并查集
1. 双亲数组表示互不相交的集合
每个元素保存双亲下标；根结点保存负数。初始时每个元素都是根。
2. Find 沿双亲指针向上找根
int Find(int parent[], int x) {
while (parent[x] >= 0) {
x = parent[x];
}
return x;
}
最坏时间取决于树高。未优化时，树高可能达到 O(n)。
3. 按规模合并让树尽量矮
void UnionBySize(int parent[], int a, int b) {
int rootA = Find(parent, a);
int rootB = Find(parent, b);
if (rootA == rootB) return;
if (parent[rootA] > parent[rootB]) {
int tmp = rootA; rootA = rootB; rootB = tmp;
}
parent[rootA] += parent[rootB];
parent[rootB] = rootA;
}
根结点保存负的集合规模，因此规模越大，数值越小。
4. 路径压缩改写查找路径
int FindCompress(int parent[], int x) {
if (parent[x] < 0) return x;
parent[x] = FindCompress(parent, parent[x]);
return parent[x];
}
找到根后，路径上的每个结点都直接指向根。配合按规模合并后，常见规模下操作开销接近常数。