> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/201-400/261.-yi-tu-pan-shu.md).

# 261.以图判树

[付费题](https://leetcode-cn.com/problems/graph-valid-tree/)

给定从 0 到 n-1 标号的 n 个结点，和一个无向边列表（每条边以结点对来表示），请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。

示例 1：

输入: n = 5, 边列表 edges = \[\[0,1], \[0,2], \[0,3], \[1,4]] 输出: true 示例 2:

输入: n = 5, 边列表 edges = \[\[0,1], \[1,2], \[2,3], \[1,3], \[1,4]] 输出: false

注意：你可以假定边列表 edges 中不会出现重复的边。由于所有的边是无向边，边 \[0,1] 和边 \[1,0] 是相同的，因此不会同时出现在边列表 edges 中。

## 一、并查集

对每条变的顶点a、b，首先测试连通性，若已连通说明将这条边添加会产生环，否则不会

```python
# 并查集代码略
class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        uf = UnionFind(n)
        for a, b in edges:
            if uf.isConnected(a, b):	#若ab连通，则这条边不能加入，直接返回
                return False
            uf.union(a, b)	#否则将ab连通
        return uf.count == 1	#最后还要看连通分量是否为1，若不为1也不是树
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/201-400/261.-yi-tu-pan-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.