图
并查集
并查集，又称不相交集合数据结构，用来管理一批被划分成若干组的元素，并能飞快地回答一个问题：这两个元素在不在同一组？它支持两种操作：find（这个元素属于哪一组？）和 union（把含这两个元素的两组合并）。可以把它想成朋友圈——并查集能瞬间告诉你两个人是否已经在同一个圈子里，并把两个圈子合并成一个。
每一组被存成一棵树，每个元素指向一个父节点，树根就是这一组的代表。find 沿着父指针一路走到根；union 把一个根挂到另一个根之下。如果朴素地做，这些树会越长越高、越来越慢，所以要同时施加两项优化。路径压缩在 find 过程中把途经的元素直接指向树根，从而把树压扁。按秩（或按大小）合并总是把矮的树挂到高的树之下，让树保持低矮。
同时用上这两项优化后，每次操作的摊还代价实际上是常数级——严格地说是 O(alpha(n))，其中 alpha 是反阿克曼函数，对你这辈子会遇到的任何输入它都不超过约 4。这种近乎 O(1) 的速度使并查集成为 Kruskal 算法内部的引擎——它能在常数时间内判断加入一条边是否会形成环——也使它成为连通性与分组类问题的常备工具。
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // path compression
return parent[x];
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (rank_[a] < rank_[b]) swap(a, b);
parent[b] = a;
if (rank_[a] == rank_[b]) ++rank_[a];
}find 把途经的每个节点直接指向根；union 把矮树挂到高树之下。
反阿克曼函数 alpha(n) 增长极慢，对任何实际的 n 都小于 5，所以人们常直接说并查集“每次操作实际上是 O(1)”。
又称
另见