LeetCode Q323: Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

     0          3
     |          |
     1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

     0           4
     |           |
     1 --- 2 --- 3

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Solution 1:

BFS

	class Solution {
	public:
	int countComponents(int n, vector<pair<int, int>>& edges) {
	vector<vector<int> > links(n);
	for(int i=0; i<edges.size(); i++){
	pair<int, int> p = edges[i];
	links[p.first].push_back(p.second);
	links[p.second].push_back(p.first);
	}
	vector<int> visited(n, 1);
	int res=0;
	for(int i=0; i<links.size(); i++){
	if(links[i].size()==0)
	continue;
	res++;
	queue<int> myQ;
	myQ.push(i);
	while(!myQ.empty()){
	int front = myQ.front();
	visited[front]=0;
	myQ.pop();
	for(int j=0; j<links[front].size(); j++){
	int p=links[front][j];
	if(links[p].size()!=0)
	myQ.push(p);
	for(int k=0; k<links[p].size(); k++){
	if(links[p][k]==front){
	int tmpp = links[p][links[p].size()-1];
	links[p][links[p].size()-1]=links[p][k];
	links[p][k]=tmpp;
	links[p].pop_back();
	break;
	}
	}
	}
	while(!links[front].empty())
	links[front].pop_back();
	}
	}
	for(int i=0; i<n; i++)
	res=res+visited[i];
	return res;
	}
	};

view raw Q323.cpp hosted with ❤ by GitHub

Solution 2:
Union Find

	class Solution {
	public:
	int find(vector<int>& roots, int id){
	while(roots[id] != id){
	roots[id] = roots[roots[id]];
	id = roots[id];
	}
	return id;
	}
	int countComponents(int n, vector<pair<int, int>>& edges) {
	vector<int> roots(n);
	for(int i=0; i<n; i++)
	roots[i]=i;
	for(int i=0; i<edges.size(); i++){
	int root1 = find(roots, edges[i].first);
	int root2 = find(roots, edges[i].second);
	if(root1!=root2){
	roots[root1]=root2;
	n--;
	}
	}
	return n;
	}
	};

view raw Q323-1.cpp hosted with ❤ by GitHub