C语言并查集详解（从零开始掌握并查集数据结构）

并查集的基本实现（C语言）

我们用一个整型数组 parent[] 来表示每个元素的父节点。初始时，每个元素的父节点是自己，即 parent[i] = i。

1. 初始化

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

2. Find 操作（查找根节点）

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

这个版本的 find 是最朴素的，时间复杂度在最坏情况下可能达到 O(n)。

3. Union 操作（合并两个集合）

void unionSet(int parent[], int x, int y) {    int rootX = find(parent, x);    int rootY = find(parent, y);    if (rootX != rootY) {        parent[rootX] = rootY;  // 将 rootX 的父节点设为 rootY    }}

优化：路径压缩 + 按秩合并

为了提升效率，我们可以对并查集进行两种经典优化：

1. 路径压缩（Path Compression）：在 find 时，将路径上的所有节点直接指向根节点，减少后续查找时间。
2. 按秩合并（Union by Rank）：合并时，总是将较小的树接到较大的树下，避免树过高。

优化后的代码实现

#include <stdio.h>#include <stdlib.h>#define MAXN 1000int parent[MAXN];int rank[MAXN];  // 用于记录树的高度（秩）// 初始化void init(int n) {    for (int i = 0; i < n; i++) {        parent[i] = i;        rank[i] = 0;    }}// 带路径压缩的 findint find(int x) {    if (parent[x] != x) {        parent[x] = find(parent[x]);  // 递归压缩路径    }    return parent[x];}// 按秩合并的 unionvoid 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    }}// 示例：判断两个元素是否在同一集合int isConnected(int x, int y) {    return find(x) == find(y);}// 主函数测试int main() {    int n = 5;    init(n);    unionSet(0, 1);    unionSet(2, 3);    unionSet(1, 2);    printf("0 和 3 是否连通? %s\n", isConnected(0, 3) ? "是" : "否");    printf("0 和 4 是否连通? %s\n", isConnected(0, 4) ? "是" : "否");    return 0;}

经过优化后，并查集的每次操作平均时间复杂度接近常数级别（阿克曼函数的反函数），效率极高！

应用场景

• 图的连通性判断（如 Kruskal 最小生成树算法）
• 社交网络中的好友关系合并
• 动态连通组件检测
• 等价类问题（如判断变量是否相等）

总结

通过本篇并查集教程，你应该已经掌握了 C 语言中并查集实现的基本方法和优化技巧。记住：初始化、Find、Union 是三大核心，而路径压缩与按秩合并是性能的关键。

多加练习，你就能在各类算法竞赛或工程问题中灵活运用这一强大工具！

如果你觉得这篇教程有帮助，欢迎分享给更多学习 C语言并查集 的小伙伴！