261. Graph Valid Tree

Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], returntrue.

0 ----- 3
|\
| \ 
|  \       
1   2 
|
4

Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], returnfalse.

0---1--2
    /\/
    |/\ 
    3   4

Note: you can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges.

Thoughts:

1. Use Union-Find to detect cycles: a. initialize an array of size as number of nodes in the graph with a value as -1. b. for each edge, explore their "roots" , if their roots are not the same, replace the root of one to the other (make them connected); otherwise, if their roots are the same, it means two nodes are already belong to the same connected components, add add extra edge would result in cycle.

2. Time Complexity O(n * len(edges))-> since each time of exploring edges there might be at most n - 1 traversing to find the current node's root. Space Complexity: O(n)

Code

class Solution {
public:
    bool validTree(int n, vector<pair<int, int>>& edges) {
        int m = edges.size();
        if(n < 1 || edges.size()!= n - 1) return false;

        int roots[n];
        fill_n(roots, n, -1);
        for(pair<int,int> p: edges){
            int roota = find(roots, p.first);
            int rootb = find(roots, p.second);
            // cycle detection
            if(roota == rootb) return false;
            roots[roota] = rootb;
        }

        return true;
    }

    int find ( int roots [], int v){
        while(roots[v] != -1) v = roots[v];
        return v;
    }
};