AlenAntonelli

Graph Connectivity

May 25th, 2018
555
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. using namespace std;
  5.  
  6. struct graf {
  7.     vector< vector<int> > adj;
  8.     vector<bool> visit;
  9.     string linea;
  10.     int k, n;
  11.    
  12.     void DFS (int nodo)
  13.     {
  14.         visit[nodo] = true;
  15.        
  16.         for (int i=0; i<adj[nodo].size(); i++)
  17.         {
  18.             int vecin = adj[nodo][i];
  19.             if ( !visit[vecin] )
  20.                 DFS(vecin);
  21.         }
  22.     }
  23.    
  24.     int contar_componentes()
  25.     {
  26.         int c = 0;
  27.         for (int i=0; i<n; i++)
  28.             if (!visit[i])
  29.             {
  30.                 c++;
  31.                 DFS(i);
  32.             }
  33.        
  34.         return c;
  35.     }
  36.    
  37.     void read ()
  38.     {
  39.         cin>>k;
  40.        
  41.         getline(cin,linea);
  42.         getline(cin,linea);
  43.        
  44.         for (int i=0; i<k; i++)
  45.         {
  46.             getline(cin,linea);
  47.            
  48.             n = 1 + linea[0] - 'A';
  49.            
  50.             adj.clear();
  51.             adj.resize(n);
  52.             visit = vector<bool> (n, false);
  53.            
  54.             getline(cin,linea);
  55.             while ( linea.size() )
  56.             {
  57.                 int a = linea[0]-'A';
  58.                 int b = linea[1]-'A';
  59.                
  60.                 adj[a].push_back(b);
  61.                 adj[b].push_back(a);
  62.                
  63.                 getline(cin,linea);
  64.             }
  65.            
  66.             cout << contar_componentes();
  67.             if ( (1+i)<(k) )
  68.                 cout << endl << endl;
  69.         }
  70.     }
  71. };
  72.  
  73. int main()
  74. {
  75.     graf g;
  76.     g.read();
  77.    
  78.     return 0;
  79. } /*
  80.  
  81. 2
  82.  
  83. E
  84. AB
  85. CE
  86. DB
  87. EC
  88.  
  89. G
  90. AB
  91. BC
  92. CD
  93. EF
  94.  
  95. */
Advertisement
Add Comment
Please, Sign In to add comment