LeetCode:261. 以图判树 - Python

261. 以图判树

问题描述：

给定从 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 中。

问题分析：

这题目有点贵呀，是LeetCode的VIP题目，第一次见还有点蒙，其实仔细想想也没啥难的。问题分析，判断一个无向图能否勾成一个树，很显然这个图要满足3个条件：

1. 这个图不存在环
2. 这个图所有节点是连通
3. 这个图的边数一定为 n-1， 因为如果一棵树有n个节点，那么它的边一定是n-1
4. 是不是可以得出这样的结论：如果有n-1条边且有环是一定是不连通，是不是可以说明，在n-1条边的条件下，只要判断是否有环即可？没有环路且边数为n-1，就一定能构造成树？(没有严谨的证明哈，感觉反证法可以证明)

现在看看题目如何做？
（1）第一个条件就是判断这个图的边数是否等于n-1，很显然不符合就直接返回 False 即可。
（2）使用并查集的思想判断是否存在环路，如果存在环路直接返回 False，否则最后就返回 True 。

Python3实现：

# @Time   :2023/09/06
# @Author :Liu


class Solution:

    def validTree(self, n, edges):

        if len(edges) != n - 1:  # 边数是否等于 n - 1
            return False

        def find(x):  # 并查集查找
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]

        fa = [i for i in range(n)]
        for x, y in edges:  # 判断两个点是否在同一个并查集里面
            fa_x = find(x)
            fa_y = find(y)

            if fa_x == fa_y:
                return False

            fa[fa_x] = fa_y

        return True


if __name__ == '__main__':
    solu = Solution()
    n, edges = 7, [[0, 1], [1, 2], [2, 3], [4, 5], [4, 6], [5, 6]]
    print(solu.validTree(n, edges))
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

相关参考：
[1]LeetCode:261. 以图判树 是VIP 题目，反正我是打不开。
[2] 代码参考: yiduobo的每日leetcode 261.以图判树。只在本地验证了，没有在线验证。
声明： 总结学习，有问题或不当之处，可以批评指正哦，谢谢。