并查集的实现

[编程题]并查集的实现

热度指数：5600 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个没有重复值的整形数组arr，初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构，并提供以下两个操作。

boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合
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

输入

输出

No
Yes
Yes

说明

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

备注:

算法知识视频讲解

华科不平凡

发表于 2020-09-07 10:41:00

我以前也不会呀，自从用了并查集之后，嗨，效果还真好！我们全家都用它！——某大佬关于并查集，有以下题型： LeetCode130——Surrounded Regions——给了个二维 grid，把里面O全部变成X，但是边界和边界联通区域内的O保留（也能用DFS） LeetCode261——Gra 展开全文