并查集：判断“我们是不是一伙的”

Kingcq2026/7/13大约 6 分钟

并查集解决什么问题

假设班上有若干同学，他们之间有一些“朋友关系”。朋友的朋友也是朋友，所以这些人会形成一个一个的小圈子。现在的问题是：

给定两个人，他们是不是同一个圈子的？
如果让两个人成为朋友，会不会把两个原本不相干的圈子合并成一个？

这种“判断元素是否属于同一集合”以及“合并两个集合”的问题，就是并查集（Union-Find，也叫 Disjoint Set Union，DSU）的专长。

经典应用场景包括：

社交网络中的圈子判断
迷宫生成：判断两个格子是否连通
最小生成树算法 Kruskal
图像处理中的连通块标记

基本思想：每个集合选出一个“老大”

并查集用一棵或多棵树来表示集合。每个元素都有一个 parent 指针指向自己的父节点，而每棵树的根节点就是这颗集合的“老大”（代表元）。

判断两个元素是否在同一集合，只需要沿着 parent 一路往上找，看最终是否到达同一个根节点。

上图表示两个集合：{1, 2, 3} 的老大是 2，{4, 5, 6} 的老大是 5。

三个核心操作

并查集只有三个基本操作：

make_set(x)：初始化，让 x 自己成为一个集合，父节点指向自己。
find(x)：找到 x 所在集合的根节点。
union(x, y)：把 x 和 y 所在的两个集合合并。

最朴素的实现

#include <stdio.h>

#define N 100

int parent[N];

// 初始化：每个人的老大都是自己
void make_set(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;
}

// 合并：让 x 所在集合的老大指向 y 所在集合的老大
void union_set(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if (rx != ry) {
        parent[rx] = ry;
    }
}

int main(void) {
    make_set(6);

    union_set(0, 1);
    union_set(1, 2);
    union_set(3, 4);
    union_set(4, 5);

    printf("0 和 2 是否连通：%s\n", find(0) == find(2) ? "是" : "否");
    printf("0 和 3 是否连通：%s\n", find(0) == find(3) ? "是" : "否");

    union_set(2, 3);
    printf("合并后 0 和 3 是否连通：%s\n", find(0) == find(3) ? "是" : "否");

    return 0;
}

优化一：路径压缩

上面的 find 操作在最坏情况下会退化成一条长链，效率很低。

路径压缩的想法很简单：在 find 的过程中，把沿途每个节点的 parent 都直接指向根节点。这样下次再访问这些节点时，就一步就能到根。

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 递归的同时把父节点直接挂到根上
    }
    return parent[x];
}

经过路径压缩后，原来的链状结构变成了扁平的星形结构。

优化二：按秩合并

合并两个集合时，如果总是把大树挂在小树下面，树的高度会增长得比较快。按秩合并的做法是：让高度较小的树挂在高度较大的树下面，从而控制树的高度。

int parent[N];
int rank_arr[N];  // 记录每棵树的高度估计值

void make_set(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank_arr[i] = 0;
    }
}

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void union_set(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if (rx == ry) return;

    if (rank_arr[rx] < rank_arr[ry]) {
        parent[rx] = ry;
    } else if (rank_arr[rx] > rank_arr[ry]) {
        parent[ry] = rx;
    } else {
        parent[ry] = rx;
        rank_arr[rx]++;
    }
}