algo/di-yi-zhan-da78c/shou-ba-sh-03a72/kruskal-zu-e6b5b/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-03a72/kruskal-zu-e6b5b/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 1135. Conn...

https://labuladong.gitee.io/algo/di-yi-zhan-da78c/shou-ba-sh-03a72/kruskal-zu-e6b5b/

[huajiejack]

图论算法评论有点少。读完了，感谢作者！

[Sean04111]

薪王也刷题

[forexgg]

如果是树而不是图，只要满足以下两个条件：

1. 有 n 个节点和 n-1 条边。
2. 是连通的。

[forexgg]

261. Graph Valid Tree 可以试试的代码

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        uf = UnionFind(n)
        return all(uf.union(edge[0], edge[1]) for edge in edges)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_x] = root_y
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_y] += 1
        return True