第二十七讲：并查集——连通世界的“朋友圈”算法

各位同学，今天我们来聊一个非常有意思的数据结构——并查集。说实话，我第一次接触它的时候，觉得这玩意儿也太简单了吧？不就是几个数组加几个函数吗？后来在实际项目中才发现，越是简单的结构，用好了越能解决大问题。

并查集，英文叫 Union-Find，也叫 Disjoint Set。它解决的核心问题就两个：合并两个集合，以及判断两个元素是否属于同一个集合。你想想看，这像不像微信里的“朋友圈”？两个人是不是好友？两个群要不要合并？嗯，差不多就是这个意思。

一、并查集的基本原理

我们先从最朴素的想法开始。假设有 n 个元素，编号从 0 到 n-1。一开始，每个元素自己就是一个集合，自己是自己的“老大”。

我们用数组 parent[] 来记录每个元素的父节点。如果 parent[i] = i，说明 i 就是根节点，也就是这个集合的代表。

// 初始化：每个人都是自己的老大
void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

查找操作呢？就是沿着 parent 指针一直往上找，直到找到根节点。

// 查找：找老大
int find(int x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

合并操作更简单：找到两个元素的根，如果不同，就把一个根的 parent 指向另一个根。

// 合并：让两个集合的老大拜把子
void unionSets(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        parent[rootA] = rootB;  // 让 rootA 认 rootB 当老大
    }
}

看起来是不是很简单？但这里有个坑——如果合并顺序不好，树会退化成链表。我在项目中就吃过这个亏，当时处理几十万个节点，find 操作慢得像蜗牛爬。为什么会这样？你想想看，如果每次都把大树的根挂到小树的根下面，树的高度就会一直增长，最坏情况下 find 的复杂度会变成 O(n)。

二、路径压缩——让树变矮

解决上面那个问题的办法，就是路径压缩。说白了，就是在 find 的过程中，把沿途经过的所有节点直接挂到根节点下面。这样下次再找这些节点的时候，一步就能到位。

// 带路径压缩的查找
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 递归压缩路径
    }
    return parent[x];
}

我个人习惯用递归写法，简洁明了。当然你也可以用迭代写法，效果一样。路径压缩之后，find 的均摊时间复杂度就降到了 O(α(n))，其中 α(n) 是阿克曼函数的反函数，增长极慢，基本上可以认为是常数时间。

三、按秩合并——让树更平衡

路径压缩是从“查找”角度优化，按秩合并则是从“合并”角度优化。思路很简单：把矮的树合并到高的树下面，这样树的高度不会增加。

这里的“秩”可以是树的高度，也可以是树的节点数。我一般用高度，因为实现起来更直观。

// 初始化时增加 rank 数组
int rank[MAXN];

void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;  // 初始高度为 0
    }
}

// 按秩合并
void unionSets(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA == rootB) return;
    
    if (rank[rootA] < rank[rootB]) {
        parent[rootA] = rootB;
    } else if (rank[rootA] > rank[rootB]) {
        parent[rootB] = rootA;
    } else {
        parent[rootB] = rootA;
        rank[rootA]++;  // 只有秩相等时，高度才增加
    }
}

路径压缩 + 按秩合并，这两个优化一起用，并查集的性能就达到了理论最优。我曾经在一个图论项目中处理过百万级别的节点，find 操作几乎感觉不到延迟。

四、连通分量问题

并查集最经典的应用就是求连通分量。比如给你一张图，问有多少个连通块？或者动态添加边，实时查询两个点是否连通？

我举个例子。假设有 10 个节点，我们依次添加边：

// 添加边 (0,1), (2,3), (4,5), (1,2), (3,4)
unionSets(0, 1);
unionSets(2, 3);
unionSets(4, 5);
unionSets(1, 2);  // 现在 0,1,2,3 连在一起
unionSets(3, 4);  // 现在 0,1,2,3,4,5 全部连通

要统计连通分量个数，只需要遍历所有节点，统计根节点不同的个数即可：

int countComponents(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (parent[i] == i) count++;
    }
    return count;
}

这里要注意：一定要先对所有节点执行一次 find 操作，确保路径压缩完成，否则 parent[i] 可能不是真正的根。

五、Kruskal 算法中的应用

说到并查集，就不得不提 Kruskal 最小生成树算法。这个算法的核心就是：按边权从小到大排序，每次选一条边，如果它连接的两个节点不在同一个集合中，就加入生成树，并合并这两个集合。

你看，这不就是并查集的看家本领吗？

// 边的结构体
typedef struct {
    int u, v, w;  // 起点、终点、权值
} Edge;

// Kruskal 算法
int kruskal(int n, Edge edges[], int m) {
    // 1. 按权值排序
    qsort(edges, m, sizeof(Edge), cmp);
    
    // 2. 初始化并查集
    init(n);
    
    int mstWeight = 0;
    int edgeCount = 0;
    
    // 3. 遍历所有边
    for (int i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        
        // 如果 u 和 v 不在同一个集合
        if (find(u) != find(v)) {
            unionSets(u, v);
            mstWeight += w;
            edgeCount++;
            
            // 生成树有 n-1 条边就结束
            if (edgeCount == n - 1) break;
        }
    }
    
    return mstWeight;
}

这个算法的时间复杂度是 O(m log m)（排序）+ O(m α(n))（并查集操作），其中 m 是边数。在实际应用中，排序往往是瓶颈，并查集部分几乎可以忽略不计。

六、知识体系总览

下面这张图总结了并查集的核心知识点和它们之间的关系：

七、总结与经验

并查集这个数据结构，说难不难，说简单也不简单。它的精髓在于：用树的思想解决集合的合并与查询问题。我做了这么多年嵌入式开发，在动态连通性、网络拓扑分析、图像分割等领域都用到过它。

最后给大家几个建议：

• 初始化一定要做全——parent 和 rank 数组都要初始化，别漏了。
• find 一定要用路径压缩——这是性能的关键，别偷懒。
• 合并前先 find——确保你操作的是根节点，而不是普通节点。
• 统计连通分量前先压缩——否则统计结果可能不准确。

好了，这一讲的内容就到这里。并查集虽然基础，但它是很多高级算法的基石。希望大家能把它吃透，以后遇到连通性问题，第一个想到的就是它。

---