C++ union 240ms


  • 0
    Y

    To be a valid tree it require:

    1. no circle in connected node
    2. every node is connected ( in another word, they have one one root node )
    class Solution {
            public:
                int findRoot(int n, const int a[]) {
                    while (a[n] != n) {
                        n = a[a[n]];
                    }
                    return n;
                }
    
            bool validTree(int n, vector<pair<int, int>>& edges) {
                int nums[n];
                for (int i = 0; i < n; i++) {
                    nums[i] = i;
                }
                // init array which makes every node to be their own root
                for (auto p : edges) {
                    int r1 = findRoot(p.first, nums);
                    int r2 = findRoot(p.second, nums);
                    
                    if (r1 == r2) return false;
    
                    // connect(union) two nodes, make them have the same root
                    nums[r1] = r2;
                }
    
                // ensure every node is connect(since there will be no duplication)
                return edges.size() == n - 1;
            }
        };

Log in to reply
 

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