并查集学习笔记

0x00 基础知识

并查集是一种简单但又不简单的数据结构，它通常用来处理元素分组问题。

先看一道例题:

$n$ 个元素 $m$ 个操作，初始时每个元素都属于独立的集合。每次操作为合并两个元素所在的集合或询问两个元素是否在一个集合内。

容易发现这道题最大的难点就在于表示元素所在的集合。不妨设 $fa_u$ 表示 $u$ 的“帮主”，即为代表 $u$ 所在的集合的元素。那么初始时显然 $fa_u=u$ 。

合并 $x,y$ 所在的集合时，我们似乎只需要让两位“帮主”打架，让 $fa_x=fa_y$ 。

不过手玩一下就会发现这样合并显然是错的。假设现在的情况是这样的：

合并 $1$ 和 $3$ 之后：

容易发现，此时 $fa_1$ 并不是 $1$ 所在集合真正的“帮主”。所以在找 $u$ 所在的集合的“帮主”时我们需要不断让 $u=fa_u$ ，即不停跳出“小帮派”，直到 $fa_u=u$ 。

找“帮主”代码如下：

int fa[200005];
int fnd(int x)
{
    return fa[x]==x?x:fnd(fa[x]);
}

但是这个找“帮主”算法太慢了，接下来介绍两种优化：

路径压缩

容易发现，我们在找“帮主”的过程中可以记录下 $u$ 真正的“帮主”：

int fa[200005];
int fnd(int x)
{
    return fa[x]==x?x:fa[x]=fnd(fa[x]);
}

这样优化之后找“帮主”算法的时间复杂度大概是 $O(\log n)$ 的，证明可以看这里。

对于一般的题目，这个优化已经够用了。

按轶合并

若不能路径压缩，那么在合并两个集合时我们可以将“深度”大的集合合并到“深度”小的集合底下，其中“深度”表示属于这个集合的元素中找到“帮主”最多需要跳的次数。

启发式合并

可以保存集合的大小，每次让小的集合的“帮主”被大的集合的“帮主”打败，即让 $fa_{\text{小集合的“帮主”}}=\text{大集合的“帮主”}$ 。

这个优化配合上路径压缩之后找“帮主”算法的时间复杂度将被优化到 $\alpha(n)$ ，其中 $\alpha(n)$ 基本不会超过 $4$ ！

例题代码如下：（远古代码，将就着看吧）

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
using namespace std;

typedef long long lnt;

const int maxn=1e4+5;

int h[maxn];

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

int hb(int a,int b)
{
	int ar,br;
	ar=find(a);
	br=find(b);
	h[br]=ar;
}

int is(int a,int b)
{
	if(find(a)==find(b))
	{
		return 1;
	}
	return 0;
}

int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		h[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>z>>x>>y;
		if(z==1)
		{
			hb(x,y);
		}
		else if(z==2)
		{
			if(is(x,y))
			{
				cout<<"Y\n";
			}
			else
			{
				cout<<"N\n";
			}
		}
	}
	return 0;
}

0x01 小技巧

保存集合信息

有些题目需要我们维护集合的某些信息，例如大小，那么就可以让“帮主”带上这些信息。

边带权

有些时候，“帮主”对应着题目中某些特殊的元素，而我们要处理每个元素到它所对应的“帮主”的某些信息，那么我们就可以让并查集的边带上权值，在路径压缩的时候转移即可。

例如这道题，就可以维护 $dis_u$ 表示 $u$ 到“帮主”（领队）的距离。

拆点

这个小技巧也是并查集的神奇所在。

有些题目中元素会有多种状态。若有 $k$ 种，则可以把元素 $i$ 拆成 $k$ 个元素： $i,i+n,i+2n\dots i+(k-1)n$ ，这些元素分别代表状态为 $1,2,3\dots k$ 的 $i$ 。

接下来，当得知

若 $x$ 状态为 $a$ ，则 $y$ 状态一定为 $b$ ；若 $y$ 状态为 $b$ ，则 $x$ 状态一定为 $a$

这种信息时，就可以把 $x+(a-1)n$ 和 $y+(b-1)n$ 合并到一个集合里，表示它们是同一种情况。

这样就可以通过已知条件求出所有可能的状态，并且若同一个元素的不同状态所代表的元素在一个集合里那么就说明无解。

例如 P2024 [NOI2001] 食物链这题，就可以用 $x,x+n,x+2n$ 分别表示 $x$ 是 $A$ 、 $x$ 是 $B$ 和 $x$ 是 $C$ 的情况。

0x00 基础知识

0x01 小技巧

0x02 练习题目

感谢您的支持，我会继续努力的!