并查集
朴素并查集
并查集这一数据结构主要维护集合中的合并与查询操作。
并查集本身是一个森林，每一棵树代表每一个集合。
并查集中用 \(f[x]\) 表示 \(x\) 的父亲节点。
注意，这里并查集中每棵树的祖先即为当前集合的代表元素，也可以理解为编号，只要 \(x\) 和 \(y\) 的祖先一样就说明他们所在同一集合。
初始化
还没有进行读入时，每一个点单独为一个集合，即\(f[x]=x\)
合并操作
每次合并两个元素，即将两个元素所在的集合合并，等价于将两个集合（树）的祖先合并。既然都合并为一个集合了，祖先关系就不重要了，所以可以将一个集合的祖先变成另一个集合的祖先的儿子（顺序不重要），这样就合并了两个集合。
void Union (int u, int v) { // 合并操作int fx = find(u); // find为查询节点祖先(所在集合)int fy = find(v);if (fx != fy) { // 此条件在点带权并查集中非常重要，当且仅当x和y不在同一集合中才进行合并f[fx] = fy; // x的祖先的父亲为y的祖先，完成合并}
}
查询操作
查询某元素所在集合。每次递归 \(f[x]\) 即可。
int find (int u) {if (f[u] = u) return u; // 如果当前节点的父亲为本身，说明此节点为根节点，直接返回return find(f[u]); // 递归查询u的父亲节点的祖先
}
路径压缩
路径压缩是并查集非常非常重要的一个操作。
当这棵树为一条链是，查询操作的时间复杂度会非常高，那么就要引入这个路径压缩优化。
路径压缩，就是将一条到根节点的路径上的所有点的父亲绑定为其根节点，如下图：
路径压缩前：
路径压缩后：
路径压缩后时间复杂度来到了 \(\Theta(\alpha(n))\) (\(\alpha(n)\)为 \(n\) 的阿克曼函数的反函数，大概为常数级别)
int find (int u) {if (f[u] = u) return u; // 如果当前节点的父亲为本身，说明此节点为根节点，直接返回return f[u] = find(f[u]); // 递归查询u的父亲节点的祖先
}
并查集的启发式合并
先说一下树上启发式合并：树上启发式合并基本是根据两棵树的深度合并，深度小的合并到深度大的树上去。但是并查集的启发式合并不太一样，因为并查集是有路径压缩操作的，所以每棵树的深度都一样，那么就要根据树的节点个数来合并，节点少的合并到节点多的树上去。
这只是一个优化操作，可写可不写。
点带权并查集
点带权并查集，顾名思义，指每个点上带有权值的并查集。点权可能为其集合内元素个数或其他值，根据具体题目具体分析。但是点带权并查集维护点权的操作还是基本一样的，我们就拿元素个数为例，\(num[i]\) 表示 \(i\) 所在的集合内的元素个数。
首先初始化，因为最开始是单个节点为一个集合，有 \(n\) 个集合，所以每个集合最开始元素个数都为 \(1\)
int f[maxn], num[maxn];
for (int i = 1; i <= n; i++) {f[i] = i;num[i] = 1;
}
然后是查询操作，这里查询操作与朴素并查集是一样的。
int find (int u) {if (f[u] = u) return u;return f[u] = find(f[u]);
}
这里的合并操作有点区别，区别就在于合并时我们要维护点权的正确性。具体维护方法也很简单，假设要合并 \(x\) 和 \(y\) 所在集合，\(x\) 祖先为 \(fx\) ，\(y\) 的祖先为 \(fy\) ，不妨让 \(fx\) 为根节点的树合并到 \(fy\) 这里，也就是 \(f[fx]=fy\) ，然后 \(fy\) 集合的元素个数就需要加上 \(fx\) 集合的元素个数，也就是 \(num[fy]=num[fy]+num[fx]\) ，这样就完成了合并。这里注意一个点，当且仅当 \(fx \neq fy\) 时才能合并，要不然会出现重复合并的情况。代码如下：
void Union (int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy) {f[fx] = fy;num[fy] += num[fx];}
}
边带权并查集
边带权并查集也比较好理解，就是带有边权的并查集。边权可能为任何值，但维护起来都一样，这里以点到根节点距离为边权， \(dis[i]\) 表示 \(i\) 到根节点的距离。
注意一点，边带权与点带权还不一样的一个点是边带权在查询和合并操作中都要维护权值。
首先是查询操作，在查询操作中顺便算出 \(dis\) ，利用递归思想，直接看代码注释吧。
int find (int x) {if (f[x] == x) return x;int root = find(f[x]); // 这里先算出他祖先的dis，一层层递归下来dis[x] += dis[f[x]]; // 当前节点的dis即为他父亲的dis加上他本身的disreturn f[x] = root;
}
然后是合并操作，合并 \(x\) 和 \(y\) 时，让 \(x\) 所在集合变为 \(y\) 所在集合的子树（也就是\(f[fx]=fy\)），相应的 \(x\) 的距离就变为 \(y\) 的距离加一，也就是 \(dis[x] = dis[y]+1\)。代码：
void Union (int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy) {fa[fx] = fy;dis[x] = dis[y] + 1;}
}
这里也有一个非常重要的点，每次输出\(dis\)之前要执行一遍\(find\)函数以确保答案正确。如：
scanf("%d", &u);
find(u);
printf("%d\n", dis[u]);
种类并查集
种类并查集主要维护的是一种：敌人的敌人是朋友的一种关系。普通的并查集只能维护 \(a,b\) 是否为朋友或者 \(a,b\) 是否为敌人。
这里对于输入 \(a,b\) 为敌人关系，则 \(a\) 与 \(b+n\) 为朋友关系，并且 \(b\) 与 \(a+n\) 也是朋友关系，就进行合并。
简单来说就是并查集维护朋友关系，如果是敌人关系，则与其 \(+n\) 为朋友关系，也就是 \(a\) 与 \(a+n\) 为敌人关系。
这样说可能不太好理解，给出一道例题：
题目描述
当我们有相同的敌人时，我们就是朋友，也就是说 敌人的敌人是朋友
基于这一点，小可做了一项研究：会不会存在两个人 既是朋友又是敌人的关系，给出 \(n\) 个人，以及他们之间的 \(m\) 个敌对关系，请分析会不会存在上述关系。
输入描述
多组输入：
第一行输入一个数 \(t\) ，表示样例组数
接下来的 \(t\) 组：
每组的第一行：输入两个整数 \(n\) 和 \(m\) ，表示 \(n\) 个人，\(m\) 个敌对关系
每组的接下来 \(m\) 行：每一行输入两个数字，\(a\) 和 \(b\) ，表示 \(a\) 和 \(b\) 是敌人关系
输出描述
对于每组样例：
如果存在 “既是朋友又是敌人” 的关系，输出 Yes，否则输出 No。
代码：
#include <bits/stdc++.h>
using namespace std;const int maxn = 4000010;int t, n, m;
int fa[maxn];int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}void Union(int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy) fa[fx] = fy;
}int main() {scanf("%d", &t);while (t--) {scanf("%d%d", &n, &m);for (int i = 1; i <= 2 * n; i++) {fa[i] = i;}bool flag = false;for (int i = 1; i <= m; i++) {int a, b;scanf("%d%d", &a, &b);if (find(a) == find(b)) {flag = true;}Union(a, b + n);Union(b, a + n);}for (int i = 1; i <= n && !flag; i++) {if (find(i) == find(i + n)) {flag = true;}}printf(flag ? "Yes\n" : "No\n");}return 0;
}