「数据结构详解·七」并查集的初步

• 「数据结构详解·一」树的初步
• 「数据结构详解·二」二叉树的初步
• 「数据结构详解·三」栈
• 「数据结构详解·四」队列
• 「数据结构详解·五」链表
• 「数据结构详解·六」哈希表
• 「数据结构详解·七」并查集的初步

---

1. 并查集的定义、构成和原理 & 代码实现

并查集(Union-find disjoint sets)，是一种处理数据之间的关系的数据结构。
并查集初始是一棵森林：

一开始，每个元素的祖先都指向自己。
我们现在将 $1,2$ 所在集合合并，就像这样：

可以发现，我们让 $1$ 的祖先指向了 $2$ 的祖先。
我们现在将 $2,3$ 所在集合合并：

我们让 $2$ 的祖先指向了 $3$ 的祖先。
经过一系列操作，就成了如下的样子：

现在问：给出任意两个元素，判断其在上图中是否在同一集合中。
根据人眼观察，我们发现有三个集合 { 1 , 2 , 3 , 4 } , { 5 , 7 , 8 } , { 6 } \{1,2,3,4\},\{5,7,8\},\{6\} {1,2,3,4},{5,7,8},{6}，做起来相对容易。
但是在电脑中，这将会使得时间、空间爆炸。
我们可以去访问这两个元素的祖先，判断是否相同。
访问元素的祖先：

int find(int x)
{
	return fa[x]==x?x:find(fa[x]);//如果该节点的根节点为自己，则停止递归，否则继续递归
}
1
2
3
4

$f{a}_i$ 即 $i$ 的祖先，故 $fa$ 初始是 $i$。
可是有的时候无限地递归会导致 TLE/MLE。
我们只关心两个元素是否在同一集合，因此我们可以做一个类似记忆化的操作：

int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);//记录最终的祖先
}
1
2
3
4

这一操作被称为路径压缩。
于是就会变成这样：

那么合并我们就可以这么写：

void merge(int x,int y)
{
	fa[find(x)]=find(y);
}
1
2
3
4

现在我们又要将 $3,7$ 所在集合合并。
我们有一下两种做法：


为了让时间复杂度降低，我们当然希望让尽可能少的元素改变祖先。
上面这个例子中，显然将 { 5 , 7 , 8 } \{5,7,8\} {5,7,8} 合并到 { 1 , 2 , 3 , 4 } \{1,2,3,4\} {1,2,3,4} 更优（即图二）。
这一操作被称为按秩合并（启发式合并）。
记 $s{z}_i$ 为 $i$ 是祖先时所处集合的集合大小（注意 $sz$ 初始均为 $1$）。
我们可以将合并改成这样：

void merge(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y) return;//避免重复处理元素个数
	if(sz[x]>sz[y]) swap(x,y);//按秩合并
	fa[x]=y;
	sz[y]+=sz[x];
}
1
2
3
4
5
6
7
8
9

有了这两个优化，并查集时间复杂度为均摊 $\Theta (\alpha (n))$，其中 $\alpha (n)$ 是反阿克曼函数，增长极其缓慢，甚至可以看作很小的常数。
一般来说，我们只要路径压缩就可以了。
并查集还有带权并查集（即边带有权值）和扩展域并查集等多个变种，这留给读者自行查阅资料与思考。
并查集也有很多应用，我们将在以后逐步讲解。

2. 例题详解

2-1. P3367 【模板】并查集

代码：

#include
using namespace std;

int a[10005];

int find(int x)
{
	if(a[x]==x) return x;
	a[x]=find(a[x]);//路径压缩
	return a[x];
}

int main()
{
	int n,m;
	cin>>n>>m;
	while(n--)
	{
		a[n+1]=n+1;
	}//初始化
	while(m--)
	{
		int z,x,y;
		cin>>z>>x>>y;
		if(z==1) a[find(x)]=find(y);//合并
		else cout<<(find(x)==find(y)?'Y':'N')<<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

2-2. P2078 朋友

这题中出现了负数，我们可以直接使用 map 处理。
我们设小明所处集合元素个数为 $x$，小红所处集合元素个数 $y$，那么答案就是 $\min (x,y)$。
对于元素个数，我们可以操作之后暴力统计。
代码：

#include
using namespace std;

map<int,int>a;

int find(int x)
{
	if(a[x]==x) return x;
	a[x]=find(a[x]);
	return a[x];
}

int main()
{
	int n,m,p,q,s=0,t=0;
	cin>>n>>m>>p>>q;
	for(int i=m*-1;i<=n;i++)
	{
		a[i]=i;//初始化
	}
	for(int i=1;i<=p+q;i++)
	{
		int x,y;
		cin>>x>>y;
		a[find(x)]=find(y);//合并
	}
	for(int i=m*-1;i<=-1;i++)//小红所处集合元素个数
	{
		if(find(a[i])==find(-1)) s++;
	}
	for(int i=1;i<=n;i++)//小明所处集合元素个数
	{
		if(find(a[i])==find(1)) t++;
	}
	cout<<min(s,t);
 	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

2-3. P1536 村村通

要想知道答案，就要知道集合个数；要想知道集合个数，我们只需要知道多少个根节点就可以了。
代码：

#include
using namespace std;

int a[1005];

int find(int x)
{
	if(a[x]==x) return x;
	a[x]=find(a[x]);
	return a[x];
}

int main()
{
 	while(1)
 	{
	 	int n,m,ans=0;
		cin>>n;
		if(!n) return 0;
		cin>>m;
		for(int i=1;i<=n;i++)
		{
			a[i]=i;
		}
		while(m--)
		{
			int x,y;
			cin>>x>>y;
			a[find(x)]=find(y);
		}
		while(n--)
		{
			if(a[n+1]==n+1) ans++;
		}
		cout<<ans-1<<endl;//一个集合对应一个根节点，故 ans 要减一
	}
}
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

3. 巩固练习

• 洛谷 P1551 亲戚
• 洛谷 UVA10685 Nature
• 洛谷 P2814 家谱
• 洛谷 P1955 [NOI2015] 程序自动分析
• *洛谷 P1196 [NOI2002] 银河英雄传说
• *洛谷 P2024 [NOI2001] 食物链