My easy to understand c++ Union Find program with explaination


  • 5
    C
    1. If the edge number is not n-1, return false;
    2. Initial the table as index same as the value;
    3. For every edge , find its boss, if they are not equal, union them and n--;
    4. At the end of program, if n is not 1, means there are more than one set, so its not a tree.
    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            if(edges.size()!=n-1) return false;
            vector<int> table(n,0);
            for(int i=0;i<n;i++){table[i] = i;}
            for(auto edge:edges){
                int boss1 = find(table,edge.first);
                int boss2 = find(table,edge.second);
                if(boss1!=boss2){
                    table[boss1] = boss2;
                    n--;
                }
            }
            return n==1? true: false;
        }
    private:
        int find(vector<int> arr, int id){
            while(id!=arr[id]){
                arr[id] = arr[arr[id]];
                id = arr[id];
            }
            return id;    
        }
    };

Log in to reply
 

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