并查集是一个用树形来表达联通关系或者集合关系的数据结构，思想很简单但是十分巧妙，主要有查找和合并两种基本操作，这种数据结构也用在了图论中最小生成树中，通常还会有一些加权值的情况和路径上的复杂关系的。
并查集
因为是树状结构的数据结构，那么根就是把各个元素联系或者说联通在一起的关键，一般称做点的“祖先”。可以先看一下 https://www.luogu.com.cn/problem/P3367 来了解一下基础概念。
一开始的所有元素都各自为一个集合，祖先就是自己本身。
// A array which represent the father of node.
int father[10010];
void Init(int n) {
for (int i = 1; i <= n; i++) {
father[i] = i;
// Initialize the father node of all elements set to itself.
}
}
查找
数据结构最重要的是通过方法与其交互来实现数据的组织，如何查找元素所属的集合和合并集合才是重头戏。下面有两种方法可以查找元素的祖先，但是不同的是其是否进行路径压缩。
这里要强调的是路径压缩会丢失链中的一些信息，不一定就是正解，可以看看这题 https://www.luogu.com.cn/problem/P2661 其中就没有使用路径压缩。
- 非路径压缩
通常要求查找的时候很容易想到由一个节点利用树的特性找到唯一的父节点即 father[a] 一直爬到最后的根节点，那么这个集合中的所有节点都可以追溯到根节点。
// Recursively find the parent node step by step.
int Find(int a) {
if (father[a] == a) {
return father[a];
} else {
return Find(father[a]);
}
}
- 路径压缩
为什么要路径压缩？因为最坏情况里，新的节点不断延长树上的其中一枝。如果想要查到该节点的祖先，算法时间效率就退化成了 $O(n)$。所以需要在查找的过程中将路径压缩防止算法退化，使下次查找的时能够更快的到达根节点。
int Find(int a) {
if (father[a] == a) {
return father[a];
} else {
father[a] = Find(father[a]);
// update parent of current node
return father[a];
}
}
不要误解并查集是菊花图，比如刚刚合并的集合就不是，并查集树是有一定深度的
不要认为认为任何情况都要路径压缩，路径压缩之后就会丢失中间节点的信息
合并
合并集合也是一个必须的操作，主要是将集合或者节点连接在另一个集合的的节点上使他们在图论概念中连通。https://www.luogu.com.cn/problem/P2078 这个题中体现出了并查集同样可以维护集合的大小。
void Merge(int a, int b) {
// B to be the father of A
father[Find(a)] = Find(b);
}
这是最正常的一种并查集集合的合并，当集合的节点具有权值的时候就是加权并查集了。比如比较难的 https://www.luogu.com.cn/problem/P1196，还有结合了背包 DP的 https://www.luogu.com.cn/problem/P1455，从这两个题中可以看出合并和查找的时候有很多复杂属性需要去维护。
- 固定合并方向
void Merge(int a, int b) {
a = Find(a), b = Find(b);
// smaller index is main set
if (a < b) {
father[b] = a;
} else {
father[a] = b;
}
}
最小生成树
解决最小生成树问题主要有 Prim 和 Kurskal 两种方法适用于无向图，其中克鲁斯卡尔算法就采用了并查集来操作生成树中的点和未加入生成树中的点。
核心算法思想
Kurskal 算法首先将带有权值的边按权值大小升序排序或者直接使用 priority_queue 来保证图中最短的路最先被访问到。每次都判断路的两端点是否属于一个集合，也就是在检查他们是否在一个连通块中。如果不在那么就需要这个目前最短的路径来让他们相连，重复该操作直到所有点相连在一个集合中。
实现代码
思路已经很清晰了，由于优先队列底层使用的比较符是小于号，如果想要升序则要重载运算符，或者直接比较函数排序也可以，看看 https://www.luogu.com.cn/problem/P3366。
struct edge {
int u;
int v;
int w;
bool operator<(const edge other) const { return this->w > other.w; }
};
// Union-find is used in Kruskal algorithm.
int father[1010];
int Find(int a) {
if (a == father[a]) {
return father[a];
} else {
father[a] = Find(father[a]);
return father[a];
}
}
void Merge(int a, int b) { father[Find(a)] = Find(b); }
priority_queue<edge> q;
int Kurskal() {
int ans = 0;
for (int i = 1; i <= n; i++) {
father[i] = i;
}
while (!q.empty()) {
edge t = q.top();
q.pop();
// If two points are not in the same set, merge sets.
if (Find(t.u) != Find(t.v)) {
Merge(t.u, t.v);
ans += t.w;
}
}
return ans;
}
问题是灵活的，有时候就需要把问题 https://www.luogu.com.cn/problem/P1195 稍微转换一下，要求 k 个连通块也可以将 n-k 个节点生成最小生成树尽量连一起，剩下的点就自成一组。