> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/10.-graph/261.-graph-valid-tree.md).

# 261. Graph Valid Tree

给你输入编号从 `0` 到 `n - 1` 的 `n` 个结点，和一个无向边列表 `edges`（每条边用节点二元组表示），请你判断输入的这些边组成的结构是否是一棵树。

函数签名如下：

```java
boolean validTree(int n, int[][] edges);
```

比如输入如下：

```shell
n = 5
edges = [[0,1], [0,2], [0,3], [1,4]]
```

这些边构成的是一棵树，算法应该返回 true：

[![](https://labuladong.github.io/algo/images/kruskal/2.png)](https://labuladong.github.io/algo/images/kruskal/2.png)

但如果输入：

```shell
n = 5
edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
```

形成的就不是树结构了，因为包含环：

[![](https://labuladong.github.io/algo/images/kruskal/3.png)](https://labuladong.github.io/algo/images/kruskal/3.png)

**对于这道题，我们可以思考一下，什么情况下加入一条边会使得树变成图（出现环）**？

显然，像下面这样添加边会出现环：

[![](https://labuladong.github.io/algo/images/kruskal/4.png)](https://labuladong.github.io/algo/images/kruskal/4.png)

而这样添加边则不会出现环：

[![](https://labuladong.github.io/algo/images/kruskal/5.png)](https://labuladong.github.io/algo/images/kruskal/5.png)

总结一下规律就是：

**对于添加的这条边，如果该边的两个节点本来就在同一连通分量(connected component)里，那么添加这条边会产生环；反之，如果该边的两个节点不在同一连通分量里，则添加这条边不会产生环**。

而判断两个节点是否连通（是否在同一个连通分量中）就是 Union-Find 算法的拿手绝活，所以这道题的解法代码如下：

```java
// 判断输入的若干条边是否能构造出一棵树结构
boolean validTree(int n, int[][] edges) {
    // 初始化 0...n-1 共 n 个节点
    UF uf = new UF(n);
    // 遍历所有边，将组成边的两个节点进行连接
    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        // 若两个节点已经在同一连通分量中，会产生环
        if (uf.connected(u, v)) {
            return false;
        }
        // 这条边不会产生环，可以是树的一部分
        uf.union(u, v);
    }
    // 要保证最后只形成了一棵树，即只有一个连通分量
    return uf.count() == 1;
}

class UF {
    // 见上文代码实现
}
```

如果你能够看懂这道题的解法思路，那么掌握 Kruskal 算法就很简单了。