并查集 - 模板
并查集，顾名思义，就是能 并(合并) 能 查(查询) 的 集(集合)
需求
- 合并集合 (一般会给你两个点，需要合并两点所在的集合)
- 询问两点是否在同一集合内
实现
思想
并查集是将某些点(可以为一个点)看作一个集合，然后有若干个集合。
因为我们只是要合并集合以及询问两点是否在同一集合之内，所以集合内点的顺序是不需要关心的。
也就是说，在一个集合的点内随便找出一个点作为(root)，其余点皆是他的儿子，这样就可以将每一个集合储存起来并为下文做好铺垫。
合并
合并极其简单，只需要将两个集合中的一个集合的(root)作为新集合的(root)，另一个集合的(root)则作为新集合(root)的儿子。
Code
//......
for(int i=1;i<=n;++i) f[i]=i;
// 初始化f数组，f[i]记录i的父亲
// 至于初始化的值，只要你能知道这个值代表ta没有爸爸而且不会与数据冲突就好
//......
int find(int x){
if(x==f[x]) return x; // ta没有父亲，所以ta是这个集合的root
return find(f[x]); // 接着寻找ta的爸爸所在集合的root (与寻找x所在集合的root等价)
}
//这个find()为查找节点x所在集合的root
//......
f[find(x)]=find(y);
//合并，找到两点所在的集合，让其中的一个root作为另一个root的儿子
//......
询问
询问依旧极其简单，只需要判断两点所在集合的(root)是否相等，相等则在一个集合内，不相等则在不同的集合内。
Code
//......
if(find(x)==find(y)) // 相同，在同一集合内
puts("Y");
else // 不相同，不在同一集合内
puts("N");
// 判断两点各所在集合的root是否相同
//......
亿些优化
- 在查询的时候，若集合内节点(设节点个数为(n))形成一条链，则查询叶子节点的复杂度为(O(n))，那么多次查找则复杂度会爆炸。
这时候，我们就需要一些优化，显然，我们可以压缩路径，在我们查询一个点((x))时，当找到这个集合的(root)的时候，我们可以直接把(x)作为(root)的儿子，这样再查询(x)节点的时候，我们就可以使用(O(1))的复杂度来解决了。
//---Code---
//......
int find(int x){
if(x==f[x]) return x;
return (f[x]=find(f[x])); // 这里使用了高(qi)超(ji)技(yin)艺(qiao)，将x的爸爸改为ta所处集合的root，下次查询效率将提升
}
//......
我不会了......
代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
#define ull unsigned ll
#define INF 0x3f3f3f3f
#define ll long long
#define GC getchar()
#define R read()
ll read(){
char c=GC; ll s=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-f;c=GC;}
while(c>='0'&&c<='9'){s=s*10+c-'0';c=GC;}
return s*f;
}
int n,m;
int op,x,y;
int f[10005];
int find(int x){ //查询其所在集合的root
if(x==f[x]) return x;
return (f[x]=find(f[x]));
}
int main(){
n=R; m=R;
for(int i=1;i<=n;++i) f[i]=i; // 初始化
for(int i=1;i<=m;++i){
op=R; x=R; y=R;
if(op==1) f[find(x)]=find(y); // 合并
else if(op==2) if(find(x)==find(y)) puts("Y"); else puts("N"); //询问
}
return 0;
}