9ms 97.08% c++ Union Find solution, applied to all Union Find questions


  • 0
    L
    class UF{
    private:
        int count;
        int* parent;
        int* rank;
    public:
        UF(int n){
            count = n;
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++){
                parent[i] = i;
                rank[i] = 0;
            }
        }
        ~UF(){
            delete parent;
            delete rank;
        }
        int find(int x){
            while(parent[x] != x){
                parent[x] = parent[parent[x]];
                x =parent[x];
            }
            return x;
        }
        int getCount(){return count;}
        bool connected(int x, int y){return find(x) == find(y);}
        void connect(int x, int y){
            int px = find(x);
            int py = find(y);
            if (px == py) return;
            if (rank[px] > rank[py]) parent[py] = px;
            else if (rank[py] > rank[px]) parent[px] = py;
            else {
                parent[px] = py;
                rank[py] ++;
            }
            count --;
        }
    };
    
    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            UF uf = UF(n);
            for (auto i :edges){
                int x = i.first, y = i.second;
                if (uf.connected(x, y)) return false;
                uf.connect(x, y);
            }
            return (uf.getCount() == 1 ? true : false);
        }
    };
    

Log in to reply
 

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