My c++ Union-Find code


  • 0
    T
    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            vector<int> p(n);
            for(int i = 0 ; i < n; ++i)
    	    p[i] = i;
    		for(auto& edge : edges){
    		int v = edge.first, w = edge.second;
    		while(p[v] != v) v = p[v] = p[p[v]];
    		while(p[w] != w) w = p[w] = p[p[w]];
    		p[v] = w;
    		if(v != w)  n -= 1;
    		else return false;//cycle detected
    	}
    	return n == 1;
        }
    };

Log in to reply
 

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