一、并查集：从概念到实战

并查集，英文叫 Union-Find，也叫 Disjoint Set Union（DSU）。

说实话，我第一次听到这个名字时，觉得它挺玄乎的。后来在项目中用多了，才发现它其实特别接地气。说白了，它就是用来解决「谁和谁是一伙的」这种问题。

1.1 并查集到底是个啥？

想象一下，你有一堆元素，每个元素一开始都是独立的个体。然后你不断告诉系统：「A 和 B 是朋友」、「B 和 C 是朋友」…… 这时候，A、B、C 就属于同一个朋友圈了。

并查集干的就是这件事：

• 合并（Union）：把两个元素所在的集合合并成一个
• 查找（Find）：判断两个元素是否在同一个集合中

我当年做社交网络分析时，就用它来快速判断两个用户是不是间接好友。嗯，效率确实高。

1.2 核心操作

并查集的核心就三个操作：

操作	说明	时间复杂度（优化后）
MakeSet(x)	创建一个只包含 x 的集合	O(1)
Find(x)	查找 x 所在集合的代表元素	O(α(n))
Union(x, y)	合并 x 和 y 所在的集合	O(α(n))

这里的 α(n) 是阿克曼函数的反函数，增长极慢。你可以认为它近似常数。也就是说，并查集的操作几乎就是 O(1) 的。

1.3 并查集的知识体系

下面这张图，是我梳理的并查集核心脉络：

二、C语言实现：从朴素到优化

2.1 朴素实现

先来个最基础的版本。每个元素用一个数组 parent[] 来记录它的父节点。一开始，每个元素的父节点就是它自己。

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000

int parent[MAXN];

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

// 查找：一直往上找，直到根节点
int find(int x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

// 合并：把 x 的根挂到 y 的根上
void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

这个版本能工作，但效率堪忧。你想想看，如果树退化成一条链，find 操作就是 O(n) 的。我早期写代码时就踩过这个坑，数据量一大直接超时。

2.2 路径压缩

路径压缩的思路很简单：在 find 的过程中，把沿途所有节点直接挂到根节点下面。这样下次再查就快多了。

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

2.3 按秩合并

按秩合并，说白了就是「小树挂到大树上」。秩可以理解为树的高度，或者树的节点数。我习惯用高度（也叫 rank）。

int rank[MAXN];  // 记录每棵树的秩

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

void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return;
    
    // 把矮的树挂到高的树上
    if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
    } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootY] = rootX;
        rank[rootX]++;  // 高度相等时，合并后高度+1
    }
}

为什么要按秩合并？因为如果不控制，树可能长得很歪。我曾经在项目中见过一个同事写的并查集，没做按秩合并，结果树高达到了几千层，find 操作慢得离谱。

2.4 完整实现（两种优化都加上）

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100000

typedef struct {
    int parent[MAXN];
    int rank[MAXN];
    int size;  // 当前元素个数
} UnionFind;

// 初始化
void init(UnionFind* uf, int n) {
    uf->size = n;
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->rank[i] = 0;
    }
}

// 查找（路径压缩）
int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

// 合并（按秩合并）
void unionSet(UnionFind* uf, int x, int y) {
    int rootX = find(uf, x);
    int rootY = find(uf, y);
    if (rootX == rootY) return;
    
    if (uf->rank[rootX] < uf->rank[rootY]) {
        uf->parent[rootX] = rootY;
    } else if (uf->rank[rootX] > uf->rank[rootY]) {
        uf->parent[rootY] = rootX;
    } else {
        uf->parent[rootY] = rootX;
        uf->rank[rootX]++;
    }
}

// 判断是否连通
int isConnected(UnionFind* uf, int x, int y) {
    return find(uf, x) == find(uf, y);
}

三、避坑指南

四、应用场景

并查集在实际开发中非常实用。我列几个常见的：

• Kruskal 最小生成树算法：判断加入一条边是否会形成环
• 社交网络中的好友关系：判断两个人是否在同一个朋友圈
• 图像处理中的连通区域标记：合并相邻的像素
• 动态连通性问题：比如网络中的节点是否连通

说实话，并查集是我个人非常喜欢的数据结构。它代码量少，逻辑清晰，效率又高。你只要把路径压缩和按秩合并这两个优化记住，基本就能应对绝大多数场景了。

---