> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/union-find/graph-valid-tree.md).

# Graph Valid Tree

<https://leetcode.com/problems/graph-valid-tree/description/>

> 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.
>
> Given n = 5 and edges = \[\[0, 1], \[1, 2], \[2, 3], \[1, 3], \[1, 4]], return false.
>
> 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

UF的另一个用途, 检测non-linear data structure是否有环. 遍历每一条边, 看边上的两个点是否已经在同一个set, 如果是代表他们之前间接连起来过, 再把它们连起来肯定会形成环, 所以返回false. 因为是检测树不是森林, 所以最后应该只有一个set.

## Code

```
class Solution {
    class UnionFind {
        int[] father;
        int size;
        UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
            size = n;
        }

        public void union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) {
                return;
            }
            father[x] = y;
            size--;
        }

        public int find(int x) {
            if (x == father[x]) {
                return x;
            }
            father[x] = find(father[x]);
            return father[x];
        }
    }

    public boolean validTree(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            if (uf.find(edge[0]) == uf.find(edge[1])) {
                return false;
            }
            uf.union(edge[0], edge[1]);
        }

        return uf.size == 1;
    }
}
```

## Analysis

时间复杂度O(N^2), N为结点数目.