文章和代码曾经归档至【Github仓库：https://github.com/timerring/algorithms-notes 】或者公众号【AIShareLab】回复 算法笔记 也可获取。
并查集
1.将两个汇合合并
2.询问两个元素是否在一个汇合当中。
基本原理:每个汇合用一棵树来示意。**树根的编号就是整个汇合的编号。**每个节点存储它的父节点，p[]示意x的父节点。
- 如何判断树根:if (p[x]== x) //它的父节点就是它本人
- 如何求x的汇合编号: while (p[x]!= x)x= p[x];
- 如何合并两个汇合:px是x的汇合编号，py是y的汇合编号。p[x]=y
优化办法
门路压缩（罕用），按秩合并。
门路压缩就是将曾经找到根节点的所有点，批改其父节点为根节点，以达到升高工夫复杂度近似为O（1）的目标。（因为若始终采纳循环来找父节点，工夫复杂度将会由树的高度决定，非常冗余）。这里是采纳递归的形式实现。
留神：通常scanf在读字符串时会主动疏忽空格和回车。因而在用scanf读入一个字符或者字母时，举荐采纳字符串的模式%S。
例题：合并汇合
一共有 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≤10^5$
输出样例：
4 5M 1 2M 3 4Q 1 2Q 1 3Q 3 4输入样例：
YesNoYescode
#include <iostream>using namespace std;const int N = 100010;int p[N];int find(int x){ // 留神这里是通过 递归 的形式进行查找并且门路压缩的 // 因为返回时逐层返回，因而会把每一层的父节点都置为根节点 if(p[x] != x) p[x] = find(p[x]); // 返回根节点 即p[x] == 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 a, b; scanf("%s%d%d", op, &a, &b); if(*op == 'M') p[find(a)] = find(b); else { if(find(a) == find(b)) puts("Yes"); else puts("No"); } } return 0;}例题：连通块中点的数量
给定一个蕴含 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≤10^5$
输出样例：
5 5C 1 2Q1 1 2Q2 1C 2 5Q2 5输入样例：
Yes23code
#include <iostream>using namespace std;const int N = 1e5 + 10;int p[N], cnt[N];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; cnt[i] = 1; } while(m --) { string op; cin >> op; int a, b; if(op == "C") { cin >> a >> b; if(find(a) == find(b)) continue; // 如果同汇合 则跳过 防止屡次合并 cnt[find(b)] += cnt[find(a)]; p[find(a)] = find(b); } if(op == "Q1") { cin >> a >> b; if(find(b) == find(a)) puts("Yes"); else puts("No"); } if(op == "Q2") { cin >> a; cout << cnt[find(a)] << endl; } } return 0;}以上的版本比拟便于了解（举荐），也能够采纳如下的写法·：
#include<iostream>using namespace std;const int N = 100010;int n, m;int p[N], cnt[N];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 op; cin >> op; int a, b; if(op == "C") { cin >> a >> b; // 留神这里是先将两个根节点取出来了 a = find(a), b = find(b); // 防止同一汇合中进行合并 if(a != b) { // 而后再进行改变 p[a] = b; cnt[b] += cnt[a]; // 如果不先取出两个根节点保留，而是间接进行操作的话，必须要先进行计数赋值，再改变根节点（即下面两句话颠倒过去，否则会造成原来的根节点产生了变动，存储的cnt也相应扭转了） } } else if(op == "Q1") { cin >> a >> b; if(find(a) == find(b)) puts("Yes"); else puts("No"); } else { cin >> a; cout << cnt[find(a)] << endl; } } return 0;}这里须要额定留神的是：a = find(a), b = find(b)先将两个根节点取出来了，如果不先取出两个根节点保留，而是间接进行操作的话，必须要先进行计数赋值，再改变根节点（否则会造成原来的根节点产生了变动，存储的cnt也相应扭转了）
图解剖析：
将1,5合并，find(1) = 3 find(5) = 4
p[3] = 4
这时候有8个点相连接，合并的数目更新形式:
- size[3] = 4 以3为根节点下有4个连通块
- size[4] = 4 以4为根节点下有4个连通块
更新4节点的连通块状况 size[4] = size[4] + size[3] = 8
模板总结
int find(int x){ // 留神这里是通过递归的形式进行查找并且门路压缩的 // 因为返回时逐层返回，因而会把每一层的父节点都置为根节点 if(p[x] != x) p[x] = find(p[x]); return p[x];}例题：食物链
动物王国中有三类动物 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 71 101 1 2 1 22 2 3 2 3 3 1 1 3 2 3 1 1 5 5输入样例：
3根本剖析
余1：能够吃根节点
余2：能够被根节点吃
余0：与根节点是同类
因而合并后，x与y同类，则能够说 d[x] + d[px] 与 d[y] 在mod3的意义下是同余的，即能够用以下式子示意
(d[x] + d[px] - d[y]) % 3 = 0 可知 d[px] = d[y] - d[x]
code
#include <iostream>using namespace std;const int N = 50010;int n, m;//p[]寻找根节点，d[]求到父节点（find更新前）/ 根节点（find更新后）的间隔int p[N], d[N];int find(int x){ if (p[x] != x) { int u = p[x]; // u记录旧的父节点 p[x] = find(p[x]); // 门路压缩，新父节点变成根节点了 d[x] += d[u]; // x到新根节点的间隔等于x到旧父节点的间隔加上旧父节点到根节点的间隔 // 以下版本不好了解： // 保留根节点 //int t = find(p[x]); // 更新间隔 d[x] = d[x] + d[p[x]] //d[x] += d[p[x]]; // 指向根节点 //p[x] = t; } return p[x];}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) p[i] = i; int res = 0; while (m -- ) { int t, x, y; scanf("%d%d%d", &t, &x, &y); // 条件2：以后的话中 X 或 Y 比 N 大，就是实话 if (x > n || y > n) res ++ ; else { // 寻找根节点 int px = find(x), py = find(y); if (t == 1) { // 若在同一个汇合 则同类相距间隔必是3的倍数 若不是则是实话 // 其中 (d[x] - d[y]) % 3 不可写为 d[x] % 3 != d[y] % 3, 因为 d[x], d[y] 可能为正数（一正一负），可改做 (d[x] % 3 + 3) % 3 != (d[y] % 3 + 3) % 3, 留神：正数 mod 负数为正数 // 相对来说间接写(d[x] - d[y]) % 3还是比拟简洁的，因为不为0就是实话 if (px == py && (d[x] - d[y]) % 3) res ++ ; else if (px != py) { // 若不在同一个汇合，x 合并到 y 中 p[px] = py; // 两个间隔相减就会变成正数，代码中有d[px] = d[y] - d[x]; d[px] = d[y] - d[x]; } } else { // 若在同一个汇合 则x吃y必满足mod3的意义下d[x]比d[y]大1 可示意为(d[x] - d[y] - 1) mod 3 = 0 if (px == py && (d[x] - d[y] - 1) % 3) res ++ ; else if (px != py) { p[px] = py; // (d[x] - d[y] - 1) % 3 == 0， d[x] + d[px] - 1 = d[y] d[px] = d[y] + 1 - d[x]; } } } } printf("%d\n", res); return 0;}⚠对于公式的具体了解：如果还是难以了解，能够尝试模仿一下过程：
1.初始状态下：
2.一般状况下：
⚠其中对于find的具体了解：
find(x)有两个性能： 1 门路压缩, 2 更新 d[x]
假如有一棵树 a -> b -> c -> d， 根节点为 d。d[b]一开始等于 b、c 之间的间隔，再执行完门路压缩命令之后，d[b] 等于b、d之间的间隔。 d[a] += d[b]: 为了确保d[a]等于 节点a、d的间隔，d[b]必须等于b 、d的间隔，所以要先调用find(b)更新d[b]， 同时p[x] = find(b)会扭转p[x]的值，后果就会变成d[a] += d[d],所以先用一个变量把p[a]的值存起来。
int t = p[x]; // t = p[a] = bp[x] = find(p[x]); // b = find(b) 每次递归都会对门路进行压缩d[x] += d[t];// d[a] = d[a](a --> b) + d[b](b --> d)// find(b):int t = p[x]; // t = p[b] = cp[x] = find(p[x]); // c = find(c)d[x] += d[t];// d[b] = d[b](b --> c) + d[c](c --> d)要害就是既要先执行find(p[x])， 又要让d[x] += d[p[x]]中p[x]的值放弃不变，所以代码能够这么写
int t = p[x];p[x] = find(p[x]);d[x] += d[t];