C语言并查集 demo

C语言中的并查集（Disjoint Set Union，DSU）是一种数据结构，常用于解决不相交集合的问题，如图的连通性检测、找出给定元素的根节点等。它维护了一组元素，每个元素都有一个代表它的“根”或“祖先”，通过合并操作可以把两个集合合并成一个。

下面是一个简单的C语言并查集的示例代码：

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

typedef struct DSU {
    int* parent;  // 存储每个元素的根索引
    int size;     // 每个集合的大小
} DSU;

// 初始化并查集
DSU* create_set(int n) {
    DSU* dsu = (DSU*)malloc(sizeof(DSU));
    dsu->parent = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        dsu->parent[i] = i;
        dsu->size = n;
    }
    return dsu;
}

// 查找根节点（路径压缩）
int find_root(DSU* dsu, int node) {
    if (dsu->parent[node] != node) {
        dsu->parent[node] = find_root(dsu, dsu->parent[node]);
    }
    return dsu->parent[node];
}

// 合并两个集合
void union_set(DSU* dsu, int node1, int node2) {
    int root1 = find_root(dsu, node1);
    int root2 = find_root(dsu, node2);

    // 如果根节点不同，合并它们
    if (root1 != root2) {
        if (dsu->size[root1] < dsu->size[root2]) {
            dsu->parent[root1] = root2;
            dsu->size[root2] += dsu->size[root1];
        } else {
            dsu->parent[root2] = root1;
            dsu->size[root1] += dsu->size[root2];
        }
    }
}

// 主函数演示
int main() {
    DSU* ds = create_set(5);
    printf("Initial sets: \n");
    for (int i = 0; i < 5; i++) {
        printf("%d -> %d\n", i, find_root(ds, i));
    }

    union_set(dsu, 0, 2);
    union_set(dsu, 3, 4);

    printf("\nAfter merging: \n");
    for (int i = 0; i < 5; i++) {
        printf("%d -> %d\n", i, find_root(ds, i));
    }

    return 0;
}

这个例子中，我们首先创建了一个包含5个元素的并查集。在`main`函数中，我们展示了如何初始化并查找每个元素的根，以及如何合并两个集合。运行这个程序，你可以看到合并操作后的结果。