Advertisement
hegemon88676

comp conexe (bf ca subprogram)

Mar 8th, 2018
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 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,nc=0,u;
  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. void BF(int start)
  16. {
  17.     int i, x,p;
  18.     p=u=1;
  19.     c[p]=start;
  20.     viz[start]=true;
  21.     nc++;
  22.     while(p<=u)
  23.     {
  24.         x=c[p];
  25.         for(i=1; i<=n; i++)
  26.             if(a[i][x]==1 && viz[i]==false)
  27.             {
  28.                 viz[i]=true;
  29.                 u++;
  30.                 c[u]=i;
  31.             }
  32.         p++;
  33.     }
  34. }
  35. int main()
  36. {
  37.     int p, b, start, i,x;
  38.     citire();
  39.     for(start=1; start<=n; ++start)
  40.     {
  41.         if(!viz[start])
  42.         {
  43.             BF(start);
  44.             cout<<"componenta conexa "<<nc<<endl;
  45.             for (i=1; i<=u; i++)
  46.                 cout<<c[i]<<" ";
  47.             cout<<endl<<endl;
  48.         }
  49.     }
  50.     cout<<"Graful are "<<nc<<" elemente conexe.\n";
  51. }
  52. /*graf.in
  53. 7
  54. 0 0 1 1 0 0 0
  55. 0 0 0 0 0 1 0
  56. 1 0 0 0 0 0 0
  57. 1 0 0 0 0 0 1
  58. 0 0 0 0 0 0 0
  59. 0 1 0 0 0 0 0
  60. 0 0 0 1 0 0 0
  61. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement