并查集

并查集（Union-Find）用于处理不相交集合的合并与查询：Union（合并两个集合）、Find（查找元素所属集合）。

存储结构

int UFSets[Size];   // 下标对应元素，值对应双亲
void Init(int S[], int n){
    for (int i = 0; i < n; i++) S[i] = -1;   // -1 表示根结点
}

基本操作

// Find：沿双亲上溯到根，O(h)
int Find(int S[], int x){
    while (S[x] >= 0) x = S[x];
    return x;
}
// Union：把 Root2 挂到 Root1 下，O(1)
void Union(int S[], int Root1, int Root2){
    S[Root2] = Root1;
}

优化策略

1. 按秩合并（Union by Rank）：将矮树合并到高树下，避免树过高。

void Union(int S[], int Root1, int Root2){
    if (Root1 == Root2) return;
    if (S[Root2] < S[Root1]) S[Root1] = Root2;   // Root2 更深
    else {
        if (S[Root1] == S[Root2]) S[Root1]--;    // 高度加 1
        S[Root2] = Root1;
    }
}

2. 路径压缩（Path Compression）：Find 时将沿途结点直接挂到根下。

int Find(int S[], int x){       // 递归版
    if (S[x] < 0) return x;
    S[x] = Find(S, S[x]);       // 路径压缩
    return S[x];
}

3. 两者结合：按秩合并 + 路径压缩，均摊 O(α(n))（α 为反阿克曼函数，近似 O(1)）。