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

  • 5
    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 {
        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);
                    table[boss1] = boss2;
            return n==1? true: false;
        int find(vector<int> arr, int 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.