并查集（模板介绍+路径压缩）

题面

P3367 并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

第一行包含两个整数 N，M，表示共有N个元素和M个操作。

接下来M行，每行包含三个整数Z，X，Y。

当Z=1时，将X与Y所在的集合合并。

当Z=2时，输出Z与 Y是否在同一集合内，是的输出 Y；否则输出 N 。

引入

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受;即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。

（摘自百度百科）

分析

如你所见，并查集一般用于维护集合之间的关系，当数据量巨大时，集合之间的操作也会变得困难。

题目的意思可以简要概括为：

1. 合并两个集合
2. 判断两个元素是否在同一集合中

如果我们用一个连通图来表示集合，其中的边数的数量级很可能将是我们无法接受的，判断是否在同一个集合中的操作也会难以实现。

而我们想到，可以用森林来实现集合的划分，一个树上的所有节点都只有一个共同的根，我们完全可以通过查找该节点所在树的根来实现判断是否位于哪个集合。

而合并操作也不难，只需要找到该元素的根，将其直接挂于另外一个元素下即可完成合并，合并后他们具有同一个根，即位于同一个集合。

建树

我们用数组来模拟森林，每个下标指向的值代表该节点的父节点。

int p[10010];
for(int i=0;i<=n;i++)
    p[i]=p[i];

初始状态下，每个节点的父节点是自己，这也代表着该节点为根节点。

功能实现

查找根节点

int find(int x)
{
	while (x != p[x]) x = p[x];
	return p[x];
}

通过迭代，我们可以一路向上，直到当x == p[x]时，找到了根节点，然后返回其根节点。

路径压缩

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

当数据过大时，树的高度会很高，这个时候查找工作所耗费的时间可能不是我们所能接受的。

那我们该如何优化查找根节点的复杂度呢。

我们可以注意到，在该题中，各个节点之间其实并没有多余的信息，也就是各节点的位置其实是不重要的，我们可以想办法让所有节点都直接挂于根节点下，这样，查找根节点的复杂度就优化到了近乎O(1)。

注：当集合中存在多余信息时我们可以多加入一颗树来维护信息，在此按下不表。

如你所见，我们用递归取代循环来实现迭代，在递归的同时，将这一脉的每一个节点的父节点都指向根节点，这样，就完成了优化。

合并集合

scanf("%d %d", &x, &y);
p[find(x)] = find(y);

如你所见，我们只需要将x的根节点的父节点指向y的父节点，就可以完成二者所在集合的合并，使用上面定义的find()函数，同时实现路径压缩，方便后续的查找。

判断共集

scanf("%d %d", &x, &y);
if (find(x) == find(y)) printf("Yes\n");
else printf("No\n");

判断共集合就更加轻而易举了，只需要判断二者元素根节点是否相同，一个if (find(x) == find(y))就可以实现，真的是非常优美啊。

代码板子

#include<cstdio>

int p[10010];
int n, m, z, x, y;

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

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i <= n; i++) p[i] = i;
	while (m--)
	{
		scanf("%d %d %d", &z, &x, &y);
		if (z == 1) p[find(x)] = find(y);
		if (z == 2)
			if (find(x) == find(y)) printf("Y\n");
			else printf("N\n");
	}
	return 0;
}

总结

这些就是最基础的并查集＋路径压缩。

并查集的代码不长，但思路却是十分优美，这种小而精悍的思维题尤其容易出现在面试当中，十分能考研一个人的思维。

与其说是集合和图论，其实具体的实现还是依靠树和递归，尤其是路径优化的递归思路，真的是非常巧妙，值得细细推敲。

以上便是对并查集的基础介绍，本文由凉茶coltea撰写，转载请注明出处。