# 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

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