并查集

并查集是一种非常高效的树形数据结构，其可以在接近 $O(1)$ 的时间复杂度来做到合并，查询一些关于一些数据之间的关系的问题。

以下内容中，$fa_x$表示节点 $x$ 的父节点。 以板题为例，其实就是有 $n$ 个节点，操作就是让你把这些的所在的集合合并或者查询是否在一个集合中。 我们可以把每一个节点在刚开始的时候定义为一个独立的点，且为一个集合的根，即 $fa_x=x$。

初始化搞定了，考虑查询节点 $x$ 的根怎么实现。 发现，当 $fa_x=x$ 时，节点 $x$ 为根。所以直接从一个节点往父亲跳，当当前阶段满足根节点的条件时，就返回当前节点。 但是，这样做的时间复杂度最慢是 $O(n)$，考虑优化。 这里要用到一个叫路径压缩的技巧，顾名思义，就是在查找的过程中将这个树里的路径压缩，发现当一个节点的根也同样是他父节点的根，所以在查询时，把查询的结果也放在 $fa_x$ 中，也就是 $fa_x=find(x)$。

合并操作在查询操作写完之后就很好写了，只用将 $x$ 的根的父节点连到 $y$ 的根上，也就是将以 $x$ 的根为根的一整棵树拼到以 $y$ 的根为根的树上，成为它的一个子树。即 $fa_{find(x)}=find(y)$。

总得时间复杂度为 $O(m\alpha(n))$，其中 $\alpha(n)$ 在对于 $n\le 10^{2^{10^{19279}}}$ 时，$\alpha(n)\le 5$。所以完全可以看作一个常数给省略掉。

并查集还可以放扩展域，即 $1$ 到 $n$ 放一组数据，$n+1$ 到 $2n$ 一组数据。

注意点 在进行合并操作时，切记是使用两个节点的根来合并的，而不是用两个点。 扩展域并查集要开双倍空间。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int fa[N];
int n,m;
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
bool same(int x,int y){
	if(find(x)==find(y))return true;
	else return false;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1)merge(x,y);
		else {
			bool f=same(x,y);
			if(f)cout<<"Y\n";
			else cout<<"N\n";
		}
	}
	return 0;
}