并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
模板题：
第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi
当Zi=1时，将Xi与Yi所在的集合合并
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N
（本体数据处理非常简单）
代码：
#include<bits/stdc++.h> using namespace std; int n,m; int fa[10005]; inline int find(int t){ //找归并在哪个集合 if(fa[t]!=t) fa[t]=find(fa[t]); return fa[t]; } inline void unity(int x,int y){ //合并集合 x=find(x); y=find(y); fa[y]=x; } int x,y,z; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){ scanf("%d%d%d",&z,&x,&y); if(z==2){ if(find(x)==find(y)) printf("Y\n"); else printf("N\n"); } if(z==1) if(find(x)!=find(y)) unity(x,y); } return 0; }
非常容易理解（借助函数名）
本题用了“路径压缩”，就是把所有的同一集合的元素的所在集合（fa数组）用同一元素（即其根元素的值）表示，更易查询。
原文：https://www.cnblogs.com/648-233/p/10776139.html