普通并查集

我们在处理问题的时候，可能会遇到一些需要维护每个元素所在的集合的问题，而并查集却恰好完美解决了这个问题。

对于普通的并查集，他支持的操作比较少，只有合并和查询，合并是指把两个集合合并成一个，而查询是询问两个元素是否在同一集合内；对于这两种操作，我们可以用一个数组 \(f\) 来存放当前点所属的集合的代表元素编号，例如，\(f[i]=3\) 表示的就是第 \(i\) 个元素属于编号为 \(3\) 的元素所在的集合，那么你可能会问了，用了这个数组，查询是好办了，我们可以直接写一个 find 函数来查询：

inline void fid(int x){return f[x]==x?x:fid(f[x]);}
//如果当前的父节点是自己就返回自己，反之返回代表元素的集合所在的代表元素编号依次直到f[x]==x;

当然我们在使用的时候发现这个 fid 如果一直往后递归会很费时间，所以我们用可以用以下的代码来优化一下：

inline void fid(int x){return f[x]==x?x:f[x]=fid(f[x]);}

这种优化也叫路径压缩，我个人的理解就是加了个记忆化。

那合并呢，咋搞？

假设我们需要把 \(x\) 和 \(y\) 所属的两个集合合并。

法一：直接暴力把所有的点遍历一遍，把所有的属于 \(y\) 所属的集合的 \(f\) 数组给暴力修改成 \(x\) 所属的集合的代表元素编号。复杂度 \(O(n)\)

法二：只修改 \(f[y]\) 的值，让他所属的集合代表元素的编号修改为 \(x\) 所属的集合代表元素的编号，后面在遇到和 \(y\) 原先属于同一集合的元素时再更新。复杂度 \(O(1)\)

很显然第一个会 T 飞，第二个复杂度很不错但是如何来实现呢？

我们之前记录的 \(f\) 数组是有大用的，配合我们的 fid 函数使我们可以轻而易举的完成法二，当你把 \(y\) 所属的集合的代表元素编号改为 \(x\) 所属的集合的代表元素编号，这样我们在后面的时候再查到所属集合为 \(y\) 所属的集合的元素时，我们就会因为 fid 函数一步一步递归更新 \(f\) 数组的值来实现法二操作了。

但是当 \(f[y]=k\) 而 \(f[k]=k\) 的时候怎么办，那样不就没法更新了吗？

所以我们在进行修改的时候改的其实并不是把 \(f[y]=f[x]\)，而是 \(f[fid(y)]=f[fid(x)]\)，直接从根源合并，这样就可以做到合并操作了。

P3367 【模板】并查集

code：

#include<bits/stdc++.h>
using namespace std;
int n,m,f[100010];
inline int fid(int x)
{
	if(f[x]==x)return x;
	else return f[x]=fid(f[x]);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  f[i]=i; 
	for(int i=1;i<=m;i++)
	{
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1)
		{
			int xx=fid(x);
			int yy=fid(y);
			f[xx]=f[yy];
		}
		else if(op==2)
		{
			int xx=fid(x);
			int yy=fid(y);
			if(xx==yy)
			  cout<<"Y"<<endl;
			else cout<<"N"<<endl;
		}
	}
	return 0;
}

扩展域并查集

我也不知道是不是叫这个名字，但是是解决 \(n\) 个点有 \(m\) 对关系，把 \(n\) 个节点放入两个集合里，要求每对存在关系的两个节点不能放在同一个集合这类的问题的一个并查集。

结合一道题目来讲一下具体怎么用：

P1892 [BOI2003]团伙

一个人的朋友的朋友是朋友
一个人的敌人的敌人是朋友