hegemon88676

comp conexe

Feb 23rd, 2018
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. ///componente conexe
  2. #include <iostream>
  3. #include <fstream>
  4. using namespace std;
  5. int c[100], a[100][100], n;
  6. bool viz[100];
  7. void citire()
  8. {
  9.     ifstream f("graf.in");
  10.     f>>n;
  11.     for (int i=1; i<=n; ++i)
  12.         for(int j=1; j<=n; j++)
  13.             f>>a[i][j];
  14. }
  15. int main()
  16. {
  17.     int p, b, start, j, nc=0, u,x;
  18.     citire();
  19.     for(start=1; start<=n; ++start)
  20.     {
  21.         if(!viz[start])
  22.         {
  23.             p=u=1;
  24.             nc++;
  25.             c[1]=start;
  26.             viz[start]=true;
  27.             while(u>=p)
  28.             {
  29.                 x=c[p];
  30.                 for(j=1; j<=n; ++j)
  31.                     if(a[j][x]&&!viz[j])
  32.                     {
  33.                         viz[j]=true;
  34.                         ++u;
  35.                         c[u]=j;
  36.                     }
  37.                 p++;
  38.  
  39.             }
  40.             cout<<"componenta conexa "<<nc<<endl;
  41.             for (j=1; j<=u; j++)
  42.                 cout<<c[j]<<" ";
  43.             cout<<endl<<endl;
  44.         }
  45.     }
  46.  
  47.     cout<<"Graful are "<<nc<<" elemente conexe.\n";
  48. }
  49. /*graf.in
  50. 6
  51. 0 1 1 0 0 0
  52. 1 0 0 0 0 0
  53. 1 0 0 0 0 0
  54. 0 0 0 0 0 1
  55. 0 0 0 0 0 0
  56. 0 0 0 1 0 0
  57. */
Advertisement
Add Comment
Please, Sign In to add comment