数据结构--并查集（Disjoint-Set）_disjoint set数据结构一

1. 并查集

• 并查集是一种树型的数据结构
• 用于处理一些不相交集合（Disjoint Sets）的合并及查询问题

2. 操作

2.1 初始化

把每个点所在集合初始化为其自身，时间复杂度均为O(N)，可用数组，哈希表等结构来实现

for(int i = 0; i < n; i++) 
	father[i] = i;
1
2

2.2 查询

查找元素所在的集合（找一个代表），即根节点
有的时候，树的高度太高，压缩树的高度，直接让底层节点的father指向root，称之路径压缩

int uniFind(int x)
{
    if(x == father[x]) 
    	return x;
    return father[x] = uniFind(father[x]);//等式为路径压缩操作
}
1
2
3
4
5
6

or 循环

int uniFind(int a)//循环+路径压缩
	{
        int origin = a;
		while(a != f[a])
			a = f[a];
		return f[origin] = a;//路径压缩
	}
1
2
3
4
5
6
7

2.3 合并

将两个元素所在的集合合并为一个集合
合并之前，先判断两个元素是否属于同一集合，用上面的uniFind操作实现

void merge(int x, int y)
{
    int fatherx = uniFind(x);
    int fathery = uniFind(y);
    if(fatherx != fathery) 
    	father[fatherx] = fathery;
}
1
2
3
4
5
6
7

2.4 孤立

father[a] = a;
1

相关题目 LeetCode 5941. 找出知晓秘密的所有专家（并查集）

3. 完整代码

/**
 * @Description: 并查集
 * @Author: michael ming
 * @Date: 2020/4/3 16:14
 * @Modified by: 
 * @Website: https://michael.blog.csdn.net/
 */
#include<bits/stdc++.h>
using namespace std;
const int n = 10;
int father[n] = {0,1,2,3,4,5,6,7,8,9};
void init()
{
    for(int i = 0; i < n; i++)
        father[i] = i;
};
int uniFind(int x)
{
    if(x == father[x])
        return x;
    return father[x] = uniFind(father[x]);//等式为路径压缩操作
}
void merge(int x, int y)
{
    int fatherx = uniFind(x);
    int fathery = uniFind(y);
    if(fatherx != fathery)
        father[fatherx] = fathery;
}
int main()
{
    init();
    merge(1,2);
    cout << "1的代表" << uniFind(1) << endl;
    cout << "2的代表" << uniFind(2) << endl;
    cout << "0的代表" << uniFind(0) << endl;
    merge(0,1);
    cout << "0的代表" << uniFind(0) << endl;
    return 0;
}
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
34
35
36
37
38
39
40

运行结果：

1的代表2
2的代表2
0的代表0
0的代表2
1
2
3
4

4. 相关题目

LeetCode 261. 以图判树（全部连通+边数=V-1）
LeetCode 305. 岛屿数量 II（并查集）
LeetCode 323. 无向图中连通分量的数目（并查集）
LeetCode 684. 冗余连接（并查集）
LeetCode 685. 冗余连接 II（并查集）
LeetCode 721. 账户合并（并查集）（字符串合并）
LeetCode 737. 句子相似性 II（并查集）
LeetCode 803. 打砖块（并查集 + 带size记录）*
LeetCode 839. 相似字符串组（并查集）
LeetCode 886. 可能的二分法（着色DFS/BFS/拓展并查集）
LeetCode 947. 移除最多的同行或同列石头（并查集）
LeetCode 990. 等式方程的可满足性（并查集）
LeetCode 959. 由斜杠划分区域（并查集）
LeetCode 1061. 按字典序排列最小的等效字符串（并查集）
LeetCode 1101. 彼此熟识的最早时间（排序+并查集）
LeetCode 1135. 最低成本联通所有城市（最小生成树+排序+并查集）
LeetCode 1202. 交换字符串中的元素（并查集）
LeetCode 1319. 连通网络的操作次数（BFS/DFS/并查集）
LeetCode 1489. 找到最小生成树里的关键边和伪关键边（并查集+kruskal最小生成树）
LeetCode 5510. 保证图可完全遍历（并查集）
LeetCode 5632. 检查边长度限制的路径是否存在（排序+并查集）
LeetCode 5650. 执行交换操作后的最小汉明距离（并查集）
程序员面试金典 - 面试题 17.07. 婴儿名字（并查集）
LeetCode 2076. 处理含限制条件的好友请求（并查集）
LeetCode 5941. 找出知晓秘密的所有专家（并查集）

5. 参考

• 并查集
• 百度百科

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！