提示：小编也是学习算法小白一枚，文章中出现错误，望请指正。

并查集概念和定义小编就不在这里赘述啦，直接上干货

一，理论支持

在讲到并查集之前小编想分享给大家一个小故事：

民间谚语：关公大战秦琼
在公元***年，关羽（二哥）想刘憨憨（刘备），离曹营过五关斩六将，来到一个隘口，书中说过了这个隘口，二哥就可以和大哥（刘憨憨团聚），这最后一关口守将不是他人，正是秦叔宝。

二哥：在下可识我？

秦叔宝：不认识，怎么着？

二哥：我大哥刘玄德你总认识吧？

秦叔宝：谁？

二哥：仁义之君，汉室正统血脉，刘玄德啊？

秦叔宝：不认识，怎么着？

二哥：三国演义没看过，文盲？

秦叔宝：没看过，反正今天就不会让你过这个关口就是。

二哥：心里嘀咕：md,碰见一个傻子，要不是我刚刚过五关斩六将累煞我也，我早就你你这个愣子干上一架了。

旁白：：这时关羽旁边的周仓站了出来。

周仓：阁下识得小编（万能buff加持）吗？

秦叔宝：这个我认识，宇宙级别的美男子，我的偶像，男神，最万能的神，我的老板。

我知道现在你们的状态： 🤮🤮🤮🤮🤮 X(乘以下面)

其实嘛，小编也没有别的意思，就是为了给大家建立一个并查集的概念及两个简单的操作。 😁😁😁😁😁

小编不闲聊啦，上正题

在这段故事中涉及了两个问题，小编在这为大家总结一来：

Ⅰ 问题1

怎么样判断两个元素（二哥和秦叔宝）是否在同一个集合（利益集团）里面。

Ⅱ 问题2

怎么样连接两个集合（利益集团），让秦叔宝和二哥成
为熟人。

文章到这，相信大家已经对并查集有了一个初步理解
但是大家心里就冒出许多问题：
（小编给大家猜一下，然后回答一下）

问题1：怎么样表示元素之间的关系？
答 ：
小编就当大家之前没有接触树这个概念来给大家讲讲。首先定义一个数组parent[N]，表示：N元素的双亲。则元素a的双亲为parent[a],同理元素b的双亲为parent[b],那么
当parent[a]=parent[b]时，意味着：元素a,b有一个相同的双亲，那么他们是亲兄弟，就是在同一个家族（集合）里面了。

问题2：怎么样判断俩个元素的祖先是否为同一个祖先？
答： 这时我们很自然的想到递归这个利器，操作如下：

写法1:
int find_parent(int x){if(x!=p[x]) p[x]=find(p[x]);return p[x];
}
写法2：
int find_parent(){while(x!=p[x]) x=p[x];return x;
}测试
int main(){int a,b;if(find(a)==find(b)) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

问题3：怎么样两个元素所属的集合连接成一个集合？
答：

if(find(a)!=find(b)){p[find(a)]=find(a);//将a集合连在b集合上面
}

二，实践运用

说了这么多，小编为大家整理了几个练习的小例子
说明：例子来源acwing

Ⅰ 例子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。
每个结果占一行。
数据范围

1≤n,m≤105

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

代码：
#include <iostream>using namespace std;
const int N=100010;
int a[N],p[N];
//find x的祖宗
int find(int x){if (p[x] != x) p[x]= find(p[x]);return p[x];
}
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){p[i]=i;}while(m--){string op;int a,b;cin>>op>>a>>b;if(op=="M") p[find(a)]=find(b);else{if(find(a)==find(b)) cout<<"Yes"<<endl;else cout<<"No"<<endl;            }}return 0;
}

Ⅱ 例子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
所在连通块中点的数量

每个结果占一行。
数据范围

1≤n,m≤105

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

代码：
#include <iostream>
using namespace std;
const int N=100010;
int cnt[N];
int p[N];
int find(int x){while(x!=p[x]) x=p[x];return x;
}
int main(){int n,m;cin >> n >> m;for (int i = 1; i <= n; i ++ ){p[i] = i;cnt[i] = 1;}while (m -- ){string op;cin >> op;if (op == "C"){int a,b;cin >> a >> b;//路径压缩a = find(a), b = find(b);if (a != b){p[a] = b;cnt[b] += cnt[a];}}else if (op == "Q1"){int a,b;cin >> a >> b;if (find(a) == find(b)) puts("Yes");else puts("No");}else{int a;cin >> a;cout << cnt[find(a)] << endl;}}return 0;}

小编：薇薇的憨宝