第8章：不相交集（Disjoint Sets / Union-Find）

一、导读

1.1 本章学习目标

第8章介绍不相交集（并查集）——一种简洁而高效的数据结构。它支持两种操作：合并两个集合（Union）和查找元素所属集合（Find）。通过路径压缩和按秩合并两种优化，可以实现近乎常数时间的操作。

本章的核心学习目标包括：

理解不相交集的抽象定义：一组互不相交的集合，支持 Union 和 Find
掌握树表示法：用树（数组）表示集合，根节点代表集合
学会两种优化：按秩合并（Union by Rank）和路径压缩（Path Compression）
理解反Ackermann函数：为什么两种优化结合后复杂度为 O(α(n))？
掌握实际应用：Kruskal最小生成树、连通性判断

1.2 为什么第八章如此重要

并查集虽然结构简单，但其分析涉及深刻的数学理论（反Ackermann函数）。它是算法设计中"简单结构+精妙分析"的典范。

在实际应用中，并查集是图算法的基础工具。Kruskal最小生成树算法的核心就是并查集。在社交网络分析、图像处理中的连通区域标记等场景中，并查集也发挥着重要作用。

1.3 核心问题引导

为什么简单的并查集实现可能退化为链表？

路径压缩如何工作？为什么它不改变树的逻辑结构？

为什么单独使用路径压缩的最坏情况仍是 O(n)？

反Ackermann函数增长有多慢？α(n) 对于所有实际规模的 n 都不超过4

Kruskal算法如何利用并查集判断是否形成环？

二、核心概念详解

8.1 基本实现

#define MAXN 10000

int parent[MAXN];
int rank_arr[MAXN];

// 初始化：每个元素自成一个集合
void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank_arr[i] = 0;
    }
}

// 查找（带路径压缩）- 摊还O(α(n))
int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // 路径压缩
    return parent[x];
}

// 合并（按秩合并）- 摊还O(α(n))
void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return;
    
    if (rank_arr[rootX] < rank_arr[rootY]) {
        parent[rootX] = rootY;
    } else if (rank_arr[rootX] > rank_arr[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootY] = rootX;
        rank_arr[rootX]++;
    }
}

// 判断是否在同一集合
int connected(int x, int y) {
    return find(x) == find(y);
}

8.2 路径压缩详解

路径压缩在 Find 操作时，将查找路径上的所有节点直接连接到根节点。

查找 find(5) 之前：        查找 find(5) 之后：
    1                           1
   /                          /|\  \
  2                          2 3   4  5
 /
3
/
4
/
5

路径压缩后，2、3、4、5都直接指向1

8.3 复杂度分析

仅按秩合并：最坏 O(log n)
仅路径压缩：最坏 O(n)（但摊还 O(log n)）
两者结合：摊还 O(α(n))，其中 α 是反Ackermann函数

反Ackermann函数增长极慢：α(n) ≤ 4 对于所有 n ≤ 2^65536。

8.4 应用：Kruskal最小生成树

typedef struct {
    int u, v, weight;
} Edge;

// 按权重排序的比较函数
int compareEdges(const void *a, const void *b) {
    return ((Edge *)a)->weight - ((Edge *)b)->weight;
}

// Kruskal算法
int kruskal(Edge edges[], int nEdges, int nVertices) {
    init(nVertices);
    qsort(edges, nEdges, sizeof(Edge), compareEdges);
    
    int mstWeight = 0;
    int mstEdges = 0;
    
    for (int i = 0; i < nEdges && mstEdges < nVertices - 1; i++) {
        int rootU = find(edges[i].u);
        int rootV = find(edges[i].v);
        if (rootU != rootV) {
            unionSet(rootU, rootV);
            mstWeight += edges[i].weight;
            mstEdges++;
        }
    }
    return mstWeight;
}
// 时间复杂度：O(E log E)（排序占主导）

三、实战案例

3.1 判断图中是否有环

int hasCycle(int edges[][2], int nEdges, int nVertices) {
    init(nVertices);
    for (int i = 0; i < nEdges; i++) {
        int rootU = find(edges[i][0]);
        int rootV = find(edges[i][1]);
        if (rootU == rootV) return 1;  // 已在同一集合，形成环
        unionSet(rootU, rootV);
    }
    return 0;
}

3.2 计算连通分量个数

int countComponents(int edges[][2], int nEdges, int nVertices) {
    init(nVertices);
    int components = nVertices;
    for (int i = 0; i < nEdges; i++) {
        int rootU = find(edges[i][0]);
        int rootV = find(edges[i][1]);
        if (rootU != rootV) {
            unionSet(rootU, rootV);
            components--;
        }
    }
    return components;
}

四、本章小结

不相交集支持 Union 和 Find 操作。

按秩合并将小树挂到大树下，控制树高。

路径压缩在查找时将节点直接挂到根下。

两者结合实现摊还 O(α(n)) 的操作复杂度。

并查集在Kruskal算法、连通性判断等问题中有重要应用。

五、思考与练习

思考题

如果只使用路径压缩而不使用按秩合并，最坏情况复杂度是多少？

如何扩展并查集以支持"删除"操作？

并查集能否用于有向图的连通性判断？

编程练习

实现带权并查集（维护每个集合的大小）。

用并查集实现一个动态连通性数据结构。

用并查集解决"等式方程的可满足性"问题。