首页 > 试题广场 >

并查集的实现

[编程题]并查集的实现
  • 热度指数：4518 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个没有重复值的整形数组arr，初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构，并提供以下两个操作。
  1. boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合
  2. void union(int a, int b): 把a所在的集合与b所在的集合合并在一起，原本两个集合各自的元素以后都算作同一个集合
[要求]
如果调用isSameSet和union的总次数逼近或超过O(N)，请做到单次调用isSameSet或union方法的平均时间复杂度为O(1)

输入描述:
第一行两个整数N, M。分别表示数组大小、操作次数
接下来M行，每行有一个整数opt
若opt = 1，后面有两个数x, y，表示查询(x, y)这两个数是否属于同一个集合
若opt = 2，后面有两个数x, y，表示把x, y所在的集合合并在一起


输出描述:
对于每个opt = 1的操作，若为真则输出"Yes"，否则输出"No"
示例1

输入

4 5
1 1 2
2 2 3
2 1 3
1 1 1
1 2 3

输出

No
Yes
Yes

说明

每次2操作后的集合为
({1}, {2}, {3}, {4})
({1}, {2, 3}, {4})
({1, 2, 3}, {4})

备注:

算法知识视频讲解
添加回答
Python
distort头像 distort
# UnionFind  并查集
# 连通分量: 自连接的点；
# 连通：自反性，等价性，传递性
# 
class UnionFind(object):
    # 构造初始连通分量为N的并查集
    def __init__(self, N):
        self.count = N
        self.parent = [ i for i in range(N)]  # 每个节点的根节点
        self.weight = [1 for _ in range(N)]  # 以节点为根的树的节点个数
    
    # 连接p,q
    def union(self, p, q):
        rootp = self.find(p)
        rootq = self.find(q)
        if rootp == rootq:
            return
        # 小树接到大树下面
        if self.weight[rootq] > self.weight[rootp]:
            self.parent[rootp] = rootq
            self.weight[rootq] += self.weight[rootp]
        else:
            self.parent[rootq] = rootp
            self.weight[rootp] += self.weight[rootq]
        self.count -= 1
    
    # 找到p的根节点     
    def find(self, p):
        while self.parent[p] != p:
            self.parent[p] = self.parent[self.parent[p]]  # 压缩树的高度降低查找耗时
            p = self.parent[p]
        return p
    
    # 判断两个节点是否连接
    def connected(self, p, q):
        rootp = self.find(p)
        rootq = self.find(q)
        return rootp == rootq
    
    # 统计连通分量个数
    def count(self):
        return self.count

            

N, times = list(map(int, input().strip().split(' ')))
uf = UnionFind(N)
i = 0
res = ''
while i < times:
    i += 1
    op, n1, n2 = list(map(int, input().strip().split(' ')))
    if op == 1:
        res += 'Yes\n' if uf.connected(n1, n2) else 'No\n'
    elif op == 2:
        uf.union(n1, n2)
print(res)
发表于 2021-02-07 21:27:56 回复(0)
提交观点

问题信息

高级结构
上传者：小小
难度：
1条回答 5801浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号