简介
并查集，是一种树形数据结构，用于维护不相交的集合。
基本原理
每个集合用一棵树来表示，树根的编号就是整个集合的编号。
每个节点存储了它的父节点。
实现
模板题（AcWing.836）
题目描述
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为 \(a\) 和 \(b\) 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b，询问编号为 \(a\) 和 \(b\) 的两个数是否在同一个集合中；
样例
in：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
out：
Yes
No
Yes
并查集实现
思路
维护一个数组 \(p\) 来表示每个节点的父节点。
判断树根
显然，如果一个节点的父节点是它本身，那它就是根节点。
代码：
inline bool is_root(ll x)
{
if(p[x]==x) return 1;
else return 0;
}
这个在本题中用不着。
合并集合
可以发现，如果要将 \(a\) 并入 \(b\) （其实等同于将 \(b\) 并入 \(a\) ），仅需在 \(a\) 的根节点和 \(b\) 的根节点间加入一条边。（原创图）
Q：那如果题目数据特别毒瘤，不间断地合并很多集合怎么办？那不就被卡成 \(\operatorname{O(n)}\) 了吗？
A：路径压缩的 find() 只会跑一遍 \(\operatorname{O(n)}\) ，就会重新变为 \(\operatorname{O(1)}\) 。
代码：
p[find(a)]=find(b);
求 \(x\) 的集合编号
递归查找。
inline ll find(ll x)
{
if(p[x]!=x) p[x]=find(p[x]);//不断查找父节点，直到找到根节点
return p[x];
}
以上代码添加了路径压缩，也就是 p[x]=find(p[x]) 在找到父节点的同时顺带更新了 p[x] 的值。
图示（原创图）：
相当于你问你爸爸你的祖先是谁，你爸爸也不知道，爸爸就去问爷爷，然后你的爷爷也不知道，爷爷就去问你的太爷爷，你的太爷爷年纪太大了，啥也不记得，就去问你的祖先。
代码
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;static char c=getchar();
while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return (f==1)?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
ll n=read(),m=read(),p[N];
inline ll find(ll x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
for(ll i=1;i<=n;i++) p[i]=i;
while(m--)
{
char op[2];ll a,b;
scanf("%s%lld%lld",op,&a,&b);//这里用 read() 会死
if(op[0]=='M') p[find(a)]=find(b);
else
{
if(find(a)==find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}