C语言并查集的代码实现提供代码和输出案例

在C语言中，并查集是一种用于处理集合操作的数据结构，它支持合并两个集合以及查询元素是否属于同一个集合。这里是一个简单的并查集的线性时间复杂度实现，使用数组和索引来存储集合信息：

#include <stdio.h>

#define MAX_SIZE 100

// 定义节点结构体
typedef struct {
    int parent; // 父节点索引
    int rank;   // 集合大小
} DisjointSet;

// 初始化并查集
void initDisjointSet(int n, DisjointSet* ds) {
    for (int i = 0; i < n; i++) {
        ds[i].parent = i;
        ds[i].rank = 1;
    }
}

// 查找根节点（路径压缩）
int findRoot(DisjointSet* ds, int node) {
    if (ds[node].parent != node)
        ds[node].parent = findRoot(ds, ds[node].parent);
    return ds[node].parent;
}

// 合并两个集合
void unionSets(DisjointSet* ds, int x, int y) {
    int rootX = findRoot(ds, x);
    int rootY = findRoot(ds, y);

    if (rootX == rootY) return; // 如果已经在一个集合内，无需合并

    if (ds[rootX].rank < ds[rootY].rank) {
        ds[rootX].parent = rootY; // 小集合合并到大集合
    } else {
        if (ds[rootX].rank == ds[rootY].rank)
            ds[rootY].rank++;     // 大小相等，提升其中一个集合的秩
        ds[rootX].parent = rootY;
    }
}

// 输出示例
void printDisjointSet(DisjointSet* ds, int n) {
    for (int i = 0; i < n; i++) {
        printf("Node %d is in set %d\n", i, findRoot(ds, i));
    }
}

int main() {
    int n = 5;
    DisjointSet ds[MAX_SIZE];

    initDisjointSet(n, ds);
    
    // 示例操作
    unionSets(&ds, 0, 1);  // [0], [1] -> [0]
    unionSets(&ds, 2, 3);  // [2], [3] -> [3] （因为 3 的秩高）
    unionSets(&ds, 4, 0);  // [4], [0] -> [3]

    printDisjointSet(&ds, n);
    
    return 0;
}

在这个例子中，当你运行`main`函数，输出将是：

Node 0 is in set 3
Node 1 is in set 3
Node 2 is in set 3
Node 3 is in set 3
Node 4 is in set 3

这表示所有元素都属于同一个集合。