1、概念
1.1集合
并查集是一个集合，它把所有具有相同属性的元素放在一个集合中。
在查找两个元素是否具有相同属性时，只需要查看他们的所在的集合是否相同就可以了。
但如果用正常的数据结构来表示，它们的空间复杂度，时间复杂度都很高，所以大多数情况，我们都用树型数据结构来表示。
1.2树型数据结构
在树型数据结构中表示并查集，一般都将根结点作为区分集合的标志。当插入新的元素时，将新的元素作为叶结点。为了优化时间复杂度，一般都尽量将各元素直接与根结点相连。
2、基本语法
2.1查询
int find(int x){
if(x!=p[x]){ //判断该节点是否为根结点
//这里可以增加一些额外的功能，比如取得结点间距离等
p[x]=find(p[x]); //通过递归，找到根节点，并把根节点作为x点的父节点。
//一般p[x]写在最后，因为大多数操作都是对x结点原本的父节点进行操作。更新p[x]后，在操作会得到错误的结果。
}
return p[x]; //返回x的父节点
}
2.2合并
int px=find(x),py=find(y); //首先获得x,y结点的根结点
if(px!=py){ //如果根节点不同，表示他们不在一个并查集中，需要合并
p[px]=py; //将y结点的根节点作为x结点的根节点
//进行合并后的其他一些附属操作(比如更新并查集中元素的个数，各元素之间的距离等等)
}
3、例题
3.1合并集合
题目
一共有n个数，编号是1~n，最开始每个数各自在一个集合中。
现在要进行m个操作，操作共有两种：
“M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
“Q a b”，询问编号为a和b的两个数是否在同一个集合中；
输入格式
第一行输入整数n和m。
接下来m行，每行包含一个操作指令，指令为“M a b”或“Q a b”中的一种。
输出格式
对于每个询问指令”Q a b”，都要输出一个结果，如果a和b在同一集合内，则输出“Yes”，否则输出“No”。
每个结果占一行。
源代码
#include <iostream>
#include <cstring>
using namespace std;
int p[100010];
int find(int x){
if(x!=p[x]){
p[x]=find(p[x]);
}
return p[x];
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
p[i]=i;
}
while(m--){
char op[2];
int x,y;
scanf("%s%d%d",op,&x,&y);
if(strcmp(op,"M")==0){
p[find(x)]=find(y);
}
else{
if(find(x)==find(y)){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
}
return 0;
}
3.2连通块中点的数量
题目
给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。
现在要进行m个操作，操作共有三种：
“C a b”，在点a和点b之间连一条边，a和b可能相等；
“Q1 a b”，询问点a和点b是否在同一个连通块中，a和b可能相等；
“Q2 a”，询问点a所在连通块中点的数量；
输入格式
第一行输入整数n和m。
接下来m行，每行包含一个操作指令，指令为“C a b”，“Q1 a b”或“Q2 a”中的一种。
输出格式
对于每个询问指令”Q1 a b”，如果a和b在同一个连通块中，则输出“Yes”，否则输出“No”。
对于每个询问指令“Q2 a”，输出一个整数表示点a所在连通块中点的数量
每个结果占一行。
源代码
#include <iostream>
#include <cstring>
using namespace std;
int p[100010],d[100010];
int find(int x){
if(x!=p[x]){
p[x]=find(p[x]);
}
return p[x];
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
p[i]=i;
d[i]=1;
}
while(m--){
char op[5];
int x,y;
scanf("%s",op);
if(strcmp(op,"C")==0){
scanf("%d%d",&x,&y);
d[find(y)]+=d[find(x)];
p[find(x)]=find(y);
}
else if(strcmp(op,"Q1")==0){
scanf("%d%d",&x,&y);
if(find(x)==find(y))
cout<<"Yes"<<endl;
else{
cout<<"No"<<endl;
}
}
else{
scanf("%d",&x);
cout<<d[find(x)]<<endl;
}
}
return 0;
}
3.3食物链
题目
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。
A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。
每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N和K句话，输出假话的总数。
输入格式
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
输出格式
只有一个整数，表示假话的数目。
源代码
#include <iostream>
#include <cstring>
using namespace std;
int p[100010],d[100010];
int find(int x){
if(x!=p[x]){
int temp=find(p[x]);
d[x]+=d[p[x]];
p[x]=temp;;
}
return p[x];
}
int main(){
int n,m,res=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
p[i]=i;
}
while(m--){
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(x>n||y>n)
res++;
else{
if(op==1){
int px=find(x),py=find(y);
if(px==py&&(d[x]-d[y])%3!=0){
res++;
}
else if(px!=py){
p[px]=py;
d[px]=d[y]-d[x];
}
}
else{
int px=find(x),py=find(y);
if(px==py&&(d[x]-d[y]-1)%3!=0){
res++;
}
else if(px!=py){
p[px]=py;
d[px]=d[y]-d[x]+1;
}
}
}
}
cout<<res<<endl;
return 0;
}
