fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. //#define FIN "dfs.in"
  5. //#define FOUT "dfs.out"
  6.  
  7. typedef unsigned long ulong;
  8.  
  9. class ConnectedComponents {
  10.  
  11.       public:
  12.  
  13.       	     //constructor of the class
  14.       	     ConnectedComponents(std::vector<std::vector<ulong>* >& adjacencyList, ulong nVertices, ulong nEdges) 
  15.       	                                           : adjList(adjacencyList), 
  16.       	                                             numVertices(nVertices), 
  17.       	                                             numEdges(nEdges),
  18.       	                                             count(0) 
  19.       	          {
  20.  
  21.       	               isVisited.resize(numVertices + 1, false);  
  22.  
  23.       	          }
  24.  
  25.       	     void execute() {
  26.  
  27.                   for(ulong node = 1; node <= numVertices; ++node) {
  28.  
  29.                           if(!isVisited[ node ]) {
  30.  
  31.                                  dfs(node);
  32.  
  33.                           	     count++;
  34.                           }
  35.  
  36.                   } 
  37.       	     } 
  38.  
  39.  
  40.       	     void dfs(ulong node) {
  41.  
  42.                   if( !isVisited[node] ) {
  43.  
  44.                        isVisited[ node ] = true;
  45.  
  46.                        if( adjList[node] ) {
  47.  
  48.                        	   for(ulong i = 0; i < adjList[node]->size(); ++i ) {
  49.  
  50.                                dfs((*adjList[node])[i] );
  51.                            }                          	   
  52.                        }
  53.                   } 
  54.  
  55.       	     }
  56.  
  57.       	     ulong getCount() const {
  58.  
  59.                    return count; 
  60.       	     }            
  61.  
  62.       private: 
  63.       	     ulong numVertices;
  64.       	     ulong numEdges;
  65.       	     std::vector<std::vector<ulong>* >& adjList;
  66.       	     ulong count;
  67.       	     std::vector<bool> isVisited;  
  68. };
  69.  
  70. int main(int argc, char const *argv[])
  71. {
  72.  
  73.     ulong n, 
  74.           m, 
  75.           x, 
  76.           y;
  77.  
  78.           std::cin>>n>>m;
  79.  
  80.           std::vector<std::vector<ulong>* > adjList;
  81.  
  82.           adjList.resize(n + 1, NULL);
  83.  
  84.           for(ulong i = 1; i <= m; ++i) {
  85.  
  86.           	  std::cin>>x>>y;
  87.  
  88.               if(adjList[x] == NULL) {
  89.               	 adjList[x] = new std::vector<ulong>();
  90.               }
  91.  
  92.               if(adjList[y] == NULL) {
  93.               	 adjList[y] = new std::vector<ulong>();
  94.               }
  95.  
  96.               adjList[x]->push_back(y);
  97.               adjList[y]->push_back(x);
  98.           }
  99.  
  100.  
  101.     ConnectedComponents connex(adjList, n, m);          
  102.                         connex.execute();
  103.                         std::cout<<connex.getCount();
  104.                         std::cout<<"\n";
  105.  
  106.  
  107.     //clean up
  108.  
  109.     for(ulong i = 0; i < adjList.size(); ++i) {
  110.  
  111.     	if(adjList[i] != NULL) delete adjList[i]; 
  112.     }                        
  113.  
  114.  
  115. 	return 0;
  116. }
Success #stdin #stdout 0s 4256KB
comments (?)
stdin
copy 
6 3
1 2
1 4
3 5
stdout
copy 
3
https://ideone.com/lxYl8e
Connected Components.
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!