Share the traditional Union-Find implementation


  • 0
    P
    class Solution {
        int zip(vector<int>&ds, int a){
                int r=a;
                while(ds[r]!=r)r=ds[r];
                int i=a;
                while(ds[i]!=r){
                    int t=ds[i];
                    ds[i]=r;
                    i=t;
                }
                return r;
        }
        int U(vector<int>& ds, int a, int b){
            int ra=zip(ds,a);
            int rb=zip(ds,b);
            ds[ra]=min(ra,rb);
            ds[rb]=ds[ra];
        }
        int F(vector<int>& ds, int a){
            return zip(ds,a);
        }
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            vector<int> ds;
            ds.resize(n);
            for(int i=0;i<n;i++){
                ds[i]=i;
            }
            for(int i=0;i<edges.size();i++){
                if(F(ds, edges[i].first)==F(ds, edges[i].second)){
                    return false;
                }else{
                    U(ds,edges[i].first, edges[i].second);
                }
            }
            for(int i=0;i<n;i++){
                zip(ds,i);
                if(ds[i]!=0){
                    return false;
                }
            }
            return true;
        }
    };

Log in to reply
 

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