题解 | #畅通工程#

畅通工程

https://www.nowcoder.com/practice/4878e6c6a24e443aac5211d194cf3913

class UnionFind:
    def __init__(self, n: int):
        self.parent = [i for i in range(n)]  # 初始化为:自己的父节点是自己
        self.rank = [0 for i in range(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):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] > self.rank[py]:  # 深度小的依附于深度大的
            self.parent[py] = self.find(px)
        elif self.rank[px] < self.rank[py]:
            self.parent[px] = self.find(py)
        else:  # 如果深度一样,则一方依附于另一方,最后记得深度加1
            self.parent[px] = self.find(py)
            self.rank[py] += 1


while True:
    try:
        ct = 0
        n, m = map(int, input().split(" "))  # n个城镇,m个道路
        if n == 0:
            break
        cz = UnionFind(n)
        for i in range(m):
            a, b = map(int, input().split(" "))
            cz.Union(a - 1, b - 1)
        for i in range(n):
            if cz.parent[i] == i:  # 如果是一个集合,则ct+1
                ct += 1
        print(ct - 1)
    except:
        break

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:02
好不容易拿到了字节Offer,鼠鼠做后端的,但家里人觉得可能被裁员不稳定,让鼠鼠去投国企,现在好纠结到底该咋选
文档传偷助手:该投就投吧,不过建议别放弃offer 拿到手里的才是最好的
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
06-12 10:50
门头沟学院 Java
你的不定积分没加C:我怎么在学院群看到了同样的话
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务