并查集
大佬笔记如下：
通俗易懂
https://zhuanlan.zhihu.com/p/93647900
并查集是什么？
主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
- 合并：把两个不相交的集合合并为一个集合。
- 查询：查询两个元素是否在同一个集合中。
作用: - 实现集合的合并与查找
- 并查集的结构：用树来存储一个集合，不过不是二叉树
- 如果两个点有共同的根，她们就在一个集合里
- 合并两个点所在集合只需要把一个点的根接到另一个点的根下面就行
注意： 并查集虽然可以进行合并操作，但是却无法进行分割操作。
亲戚问题（并查集模板题）
把所有人划分到若干个不相交的集合中，每个集合里的人彼此是亲戚。为了判断两个人是否为亲戚，只需看它们是否属于同一个集合即可。因此，这里就可以考虑用并查集进行维护。
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define bug(x) cout<<#x<<"=="<<x<<endl;
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int inf = 0xc0c0c0c0;
const int N = 2e4 + 10;
map<string, int> name;
int fa[N];
int n, m;
//查询(找祖宗)
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
//合并（认主归宗）
void merge(int x, int y) {
fa[find(x)] = find(y);
}
int main() {
ios;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
fa[i] = i; //初始化
string s;
cin >> s;
name[s] = i;
}
for (int i = 1; i <= m; i++) {
int op;
string s1, s2;
cin >> op >> s1 >> s2;
if (op == 1) merge(name[s1], name[s2]);
else {
if (find(name[s1]) != find(name[s2])) cout << 0 << endl;
else cout << 1 << endl;
}
}
return 0;
}
最简单版本的并查集代码
（1）初始化
int fa[N];
void init(int n) {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
假如有编号为\(1，2，3，...，n\)的\(n\)个元素，我们用一个数组fa[N]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。
（2）查询
写法1：
int find(int x) {
if (fa[x] == x) return x;
else return find(fa[x]);
}
写法2：
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
我们用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。沿着树向上走，来查询包含这个元素的树的根是谁。如果两个节点走到了同一个根，那么就可以知道它们属于同一组。
（3）合并
void merge(int x, int y) {
fa[find(x)] = find(y);
}
合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者。即如下图所示，从一组的根向另一组的根相连，这样两棵树就变成了一棵树，也就把两个组合并为一个组了。
路径压缩
最简单的并查集效率是比较低的。最坏情况下会形成一条长长的链，随着链越来越长，我们想要从底部找到根节点会变得越来越难。
怎么解决呢？使用路径压缩的方法。既然我们只关心一个元素对应的根节点，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步。
其实很好实现。只要我们在查询的过程中，把沿途的每个节点的父节点都设为根节点即可。下一次再查询时，就可以省很多事。这用递归写法容易实现：
合并（路径压缩）
int find(int x) {
if (x == fa[x])
return x;
else {
fa[x] = find(fa[x]); //父节点设为根节点
return fa[x]; //返回父节点
}
}
以上代码常常简写为一行:
int find(int x) {
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
注意: 赋值运算符=的优先级没有三目运算符?:高，所以这里要加括号。
路径压缩优化后，并查集的时间复杂度已经比较低了，绝大多数不相交集合的合并查询问题都能够解决。然而，对于某些时间卡得很紧的题目，我们还可以进一步优化。
按秩合并
可能的误解：以为路径压缩优化后，并查集始终都是一个菊花图（只有两层的树的俗称）。但其实，由于路径压缩只在查询时进行，也只压缩一条路径，所以并查集最终的结构任然可能是比较复杂的。例如，现在有一颗较复杂的树需要与一个单元素的集合合并：
假如这时要\(merge(7,8)\),是选择把\(7\)的父节点设为\(8\)好，还是把\(8\)的父节点设为\(7\)好呢？
当然是后者。因为如果把\(7\)的父节点设为\(8\)，会使树的深度（树中最长链的长度）加深，原来的树中每个元素到根节点的距离都变长了，之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩，但路径压缩也是会消耗时间的。而把\(8\)的父节点设为\(7\)， 则不会有这个问题，因为它没有影响到不相关的节点。
这启发我们：我们应该把简单的树往复杂的树上合并，而不是相反。因为这样合并后，到根节点距离变长的节点个数比较少。