考研笔记

板子：并查集（教材口径 + 路径压缩）

用双亲数组 S[] 表示森林：**S[x] >= 0 表示 x 的双亲；S[x] < 0 表示 x 是根，绝对值是这个集合的元素个数。**合并时小树并到大树，查找时顺便压缩路径。

代码

void Initial(int S[], int n) {               // n 个元素，各自成一个集合
    for (int i = 0; i < n; i++) S[i] = -1;   // 根的 S 为负数：-1 表示集合里只有 1 个元素
}
 
int Find(int S[], int x) {                   // 返回 x 所在集合的根，同时压缩路径
    int root = x;
    while (S[root] >= 0) root = S[root];     // 第一趟：往上走，找到根（S 为负数的那个）
    while (x != root) {                      // 第二趟：把路径上的每个结点直接挂到根下
        int t = S[x];                        // 先记下原来的双亲
        S[x] = root;
        x = t;
    }
    return root;
}
 
void Union(int S[], int Root1, int Root2) {  // 小树并到大树；两个参数都必须是根
    if (Root1 == Root2) return;              // 同一个集合，不用合并
    if (S[Root2] > S[Root1]) {               // S 是负数：S 越大，元素越少，所以 Root2 是小树
        S[Root1] += S[Root2];                // 先把元素个数加到大树的根上
        S[Root2] = Root1;                    // 再把小树的根挂过去
    } else {                                 // Root1 是小树（一样大时也走这里）
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }
}
// 合并 a、b 所在的集合：Union(S, Find(S, a), Find(S, b));

复杂度：同时使用按大小合并和路径压缩后，每次操作的均摊时间接近 （严格说是 ）。

关键边界

位置为什么
S[Root2] > S[Root1]比较的是两个负数。，所以 S 更大的那棵树元素更少
先 += 再赋值如果先执行 S[Root2] = Root1，S[Root2] 里的元素个数就被覆盖了，再加就会出错
Union 的参数必须是根不是根的话，S[] 里存的是双亲的下标，不是元素个数。所以要先 Find
一样大时 Root1 挂到 Root2 下这是教材代码的写法。选择题让画合并后的数组时，按这个规则来

算竞写法（认得就行）

// 速记：算竞写法，考场上不用
int fa[MaxSize];                             // 初始化：fa[i] = i，根满足 fa[x] == x
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

考场上按教材口径写。题目给出一个数组让你画森林时，负数的绝对值是集合的元素个数，不是树高。口径差异的完整对照见 5.5 哈夫曼树与并查集。

链接

反向链接