力扣（LeetCode）261. 以图判树（2022.09.18）

给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。

如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。

示例 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

提示：

1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= ai, bi < n
ai != bi
不存在自循环或重复的边

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/graph-valid-tree

方法一：并查集

Python提交内容：

class UnionFind:
    def __init__(self, n):
        self.part = n
        self.root = [i for i in range(n)]
        self.size = [1 for _ in range(n)]
        return

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.size[root_x] >= self.size[root_y]:
            root_x, root_y = root_y, root_x

        self.root[root_x] = root_y
        self.size[root_y] += self.size[root_x]
        self.part -= 1
        return True

    def find(self, x):
        if self.root[x] == x:
            return x
        return self.find(self.root[x])

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

    def get_part_size(self, x):
        root_x = self.find(x)
        return self.size[root_x]

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        UF = UnionFind(n)
        for x, y in edges:
            if not UF.union(x, y):
                return False
        return UF.part == 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40