> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/data-structure/union-find/graph-valid-tree.md).

# 261. Graph Valid Tree

Given`n`nodes labeled from`0`to`n - 1`and 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:

Given`n = 5`and`edges = [[0, 1], [0, 2], [0, 3], [1, 4]]`, return`true`.

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

Given`n = 5`and`edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]`, return`false`.

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

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

**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**

```cpp
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;
    }
};
```