Find number of connected component in a Graph (efficiently)

I want to find the number of all connected component in graph with details of component.

Graph is given in the form of edge.

edge 1 - a1 a2

edge 2 - b1 b2

where a1,a2,b1,b2 are vertex of graph. Please help guys.

learn about DFS/BFS

The code is shown below

//inside main if u r using vector<vector<pair<int,int> > >Graph(n);//Adjecency list representation of graph
numCC=0;
vector<int> dfs_num;
dfs_num.assign(V,DFS_WHITE) //use #define DFS_WHITE=-1;
 for(int i=0;i<V;i++){
        if(dfs_num[i]==DFS_WHITE)
         printf("Connected %d", ++numCC),dfs(i),printf("\n");
}

printf("%d",numCC);

//note dfs(i) is a procedure for depth first search

1 Like

The solution is fairly straight-forward. Number of connected components means that number of separate entities in a graph. No two entities are linked together by an edge. Start traversing the graph, from any node… let’s assume it’s node 1. Colour this node with some colour 1. Go to all neighbours of that node. Colour these nodes 1.Then go again to all neighbours of these nodes, colour them too with 1. This process stops when all the nodes of that particular entity is coloured. Then it’s time to go to the second entity. For this search for the next node(we started with 1 first) which is not coloured. Do the same process for this node with colour 2(prev colour+1). This too stops when all nodes of that entity is coloured with 2. After all the nodes are coloured, this entire routine stops. The last colour number is the number of connected components. Remember that the graph has to bi-directional for all edges.

1 Like

Thanks man but can I get a quick solution with some explanation?

There are plenty of tutorials on DFS/BFS. Wikipedia has great ones too.

Not necessarily that the edges have to be bi directional.

Recently I am started with competitive programming so written the code for finding the number of connected components in the un-directed graph. Using BFS.

I have implemented using the adjacency list representation of the graph. The Time complexity of the program is (V + E) same as the complexity of the BFS.

/*

Finding the number of non-connected components in the graph

*/

#include<bits/stdc++.h>
#define pb push_back
using namespace std;

void addEdge(vector vec[],int source,int destination){
vec[source].pb(destination);
vec[destination].pb(source);
}

void BFSUtil(vector &visited ,vector vec[],int i){

list<int> queue;

visited[i] = true;
queue.pb(i);

vector<int> :: iterator it;


if(vec[i].size()==0){
	cout<<"vec["<<i<<"].size(): "<<vec[i].size()<<endl;
	return;
}

while(!queue.empty()){
	
	i = queue.front();
	cout<<i<<" ";
	queue.pop_front();
	
	for(it = vec[i].begin(); it!= vec[i].end(); it++){
		
		if(visited[*it] == false){
			queue.pb(*it);
			visited[*it] = true;
			
		}
	}
}

}

void BFS(vector vec[],int V){

vector<bool> visited(V,false);

int total_disconnected_components = 0;
for(int i=0; i<V; i++){
	if(visited[i] == false){
		BFSUtil(visited,vec,i);
		total_disconnected_components++;
	}
}
cout<<endl;
cout<<total_disconnected_components<<endl;

}

int main(){

int t;
cin>>t;

while(t--){
	
	int v;
	cin>>v;
	
	vector<int> graph[v];
	
	int e;
	cin>>e;
	for(int i=0; i<e; i++){
		int source,destination;
		cin>>source>>destination;
		addEdge(graph,source,destination);
	}
	BFS(graph,v);
}
return 0;

}

Please let me know if any further clarification needed.

Thank you,

Novice in competitive programming world