A review of all solutions


  • 1

    This is same as graph valid tree.

    1. O(n+e) DFS
    void dfs(int from, int to, vector<bool>&vstd, vector<vector<int>> &adjlst)	{
    	if(vstd[to]) return;
    	vstd[to] = 1;
    	for(auto n:adjlst[to]) if(n!=from) dfs(to,n,vstd,adjlst);
    }
    int countComponets(int n, vector<pair<int,int>>&edges) {
    	vector<vector<int>> adjlst(n);
    	for(auto &e:edges) {
    		adjlst[e.first].push_back(e.second);
    		adjlst[e.second].push_back(e.first);
    	}
    	vector<bool> vstd(n);
    	int count = 0;
    	for(int i=0;i<n;i++) {
    		if(vstd[i]) continue;
    		count++;
    		dfs(-1, i,vstd,adjlst);
    	}
    	return count;
    }
    
    1. O(n+e) BFS
    int bfs(int n, vector<pair<int,int>>&edges) {
    	vector<unordered_set<int>> adjLst(n);
            for(auto &e:edges) {
                adjLst[e.first].insert(e.second);
                adjLst[e.second].insert(e.first);
            }
            vector<bool> vstd(n);
    	int count = 0;
    	for(int i=0;i<n;i++) {
    		if(vstd[i]) continue;
    		count++;
            	queue<int> q({i});
            	while(!q.empty()) {
               		int t = q.front();
                		q.pop();
                		if(vstd[t]) continue;
                		vstd[t] = 1;
                		for(int nb:adjLst[t]) {
                    		q.push(nb);
                    		adjLst[nb].erase(t);
                		}
            	}
    	}
            return count;
    }
    
    1. O(n+elg*n)union find
    int root (int i, vector<int> &parent) {
    	while(parent[i]!=i) i=parent[i]=parent[parent[i]];
    	return i;
    }
    int unionFind(int n, vector<pair<int,int>>&edges) {
    	vector<int> parent(n),sz(n,1);
    	iota(parent.begin(),parent.end(),0);
    	for(auto &e:edges) {
    		int r0 = root(e.first,parent), r1 = root(e.second,parent);
    		if(r0==r1) continue;
    		n--;
    		if(sz[r0]<sz[r1]) {
    			parent[r0]=r1;
    			sz[r1]++;
    		} else {
    			parent[r1]=r0;
    			sz[r0]++;	
    		}
    	}
    	return n;			
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.