本系列所有题目均为Acwing课的内容，发表博客既是为了学习总结，加深自己的印象，同时也是为了以后回过头来看时，不会感叹虚度光阴罢了，因此如果出现错误，欢迎大家能够指出错误，我会认真改正的。同时也希望文章能够让你有所收获，与君共勉！
今天来看看并查集，顾名思义，并查集的本质就是一个集合，支持快速合并集合，时间复杂度为\(\,O(1)\)，以及查找某一元素属于某个集合，时间复杂度近乎为\(\,!O(1)\)（路径压缩后的时间复杂度），除此之外，并查集还有一大优势就是支持定义额外数组来存储额外的信息，如定义数组d表示当前元素到根节点的路径长度，形成带权重的并查集，增加数组size来记录每个集合内有多少个元素，这也是后面这两道模板题所需要维护的数组。
那就先通过这道题来认识一下并查集吧！
连通块中点的数量
给定一个包含 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
算法原理
并查集的建立很简单，就是定义数组fa（Father），fa[i]表示数字i的父节点为fa[i]，使用fa[i] = i进行赋值，即每个数字的父节点最开始都是他自己，也就是每个数字代表的集合只有它自己一个元素，这个集合的祖宗节点也是他自己。
路径压缩
并查集最重要的操作就是寻找集合的祖宗节点。这里我们把并查集想象成一棵树，我们要做的就是如何找到这个树的根节点。
这个操作的主要思想就是不断访问节点的父节点看他什么时候等于x本身，如果fa[x] == x，则找到该集合的祖宗节点，并将p[x](此时p[x]与x相同)返回，如果找不到则不断搜索父节点，这个过程的时间复杂度往往与并查集的深度有关，在数据量较大时时间复杂度为\(O(n)\)，那么我们就可以使用路径压缩去优化查找祖宗节点，优化后查找的时间复杂度为\(O(1)\)，那么该怎么优化呢？
我们可以在找到根节点后，将其赋值给查找路径上的每一个结点，即fa[x] = find(fa[x])，具体的实现其实就是在递归的回归过程中把找到的祖宗节点依次赋值给路径上的每个结点，让这些路径结点的父节点直接指向祖宗节点，这时fa[x]就是祖宗节点，而不是原来的那个父节点了，也就是变成了一个深度为一层的N叉树，如图所示。
合并两个并查集
合并两个并查集可以看成是合并了两棵树，那么树该怎么合并呢，很容易就可以想到，只要让其中一个集合的父节点是另一个结合就可以啦，如对于a，b两个集合的祖宗节点，那么fa[a] = b就代表合并两个集合，也就是将集合a指向集合b的祖宗节点。
查找连通块中元素的个数
实际上就是维护了一个size数组，size[i]表示第i个集合中存在的元素个数，那么如何维护size数组呢，我们只需要初始化size中元素全为1，在合并两个并查集时顺便把集合a中元素的个数size[a]加到集合b的size[b]中就行了，即size[b] += size[a]
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int p[N],cnt[N];
int n,m;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main(){
cin >> n >> m;
for(int i=1 ; i<=n ; ++i) {
p[i]=i;
cnt[i] = 1;
}
while(m--){
string s;
int a,b;
cin >> s ;
if(s == "Q1"){
cin >> a >> b;
if(find(a) == find(b)){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
}
else if(s == "Q2"){
cin >> a;
cout << cnt[find(a)] << endl;
}
else if(s == "C"){
cin >> a >> b;
a = find(a),b = find(b);
if(a!=b){
p[a] = b;
cnt[b] += cnt[a]; // 用+=会先find(a)再find(b),这样b的位置会错
}
}
}
return 0;
}
接下来看一道关于并查集应用的题，认真理解哦。
食物链
动物王国中有三类动物 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 句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
当前的话与前面的某些真的话冲突，就是假话；
当前的话中 X 或 Y 比 N 大，就是假话；
当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入格式
第一行是两个整数 N 和 K，以一个空格分隔。
以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。
若 D=1，则表示 X 和 Y 是同类。
若 D=2，则表示 X 吃 Y。
输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤50000,
0≤K≤100000
输入样例：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例：
3
算法原理
还是先来理解一下题意吧，A吃B，B吃C，C吃A，如图。
容易知道当存在a吃b，而b吃c时，我们就能推断出c吃a。当先出现a吃b时，就不会再出现b吃a。那么我们就可以找到如图这样的关系
我们可以维护一个表示结点到根节点的距离的数组d，把食物链抽象成路径长度，假设存在一个三层的树，若某一结点到根节点的路径距离为1，则说明这个结点可以吃根节点，距离根节点长度为2的结点，说明这个结点可以吃距离为1的结点，同时也可以被根节点吃(也就对应了距离为3的结点)，那么距离根节点长度为3的结点不就是根节点的同类，它是可以吃距离为2的结点，这样就把食物链的循环转化为路径长度的循环，每3个结点就是一轮循环，即(d[x]-d[y])%3就表示x和y之间的关系，0为同类，1为x吃y，2为y吃x。
至于为什么，我们可以吧%3给弄进去，即d[x]%3-d[y]%3，d[x]%3即x与根节点的关系，d[y]%3同理，当(d[x]%3-d[y]%3) = 0时，即，x与y是同类，当(d[x]%3-d[y]%3) = 1时，x的父亲是y，即x吃y，那么当(d[x]%3-d[y]%3) = 2，x的父节点的父节点才是y，说明x与根节点是同类，y吃x。也就是说只要将结点加入到集合中，我们就能通过分别比较他们与根节点的关系来得到他们之间的关系，因此这个集合里面的结点关系都是推断出的