用C语言写一段并查集

以下是一个简单的并查集实现，使用C语言：

#include <stdio.h>
#define MAXN 1000

int p[MAXN]; // 存储每个元素的祖先节点

// 初始化并查集，每个元素的祖先节点都是自己
void init(int n) {
    for (int i = 1; i <= n; i++) {
        p[i] = i;
    }
}

// 查找元素的祖先节点
int find(int x) {
    if (p[x] == x) {
        return x;
    } else {
        return p[x] = find(p[x]); // 路径压缩
    }
}

// 合并两个元素所在的集合
void merge(int a, int b) {
    p[find(a)] = find(b);
}

int main() {
    int n = 5;
    init(n);
    merge(1, 2);
    merge(3, 4);
    merge(4, 5);
    printf("%d\n", find(1)); // 2
    printf("%d\n", find(3)); // 5
    printf("%d\n", find(4)); // 5
    return 0;
}

在这个实现中，`p`数组存储每个元素的祖先节点。在初始化时，每个元素的祖先节点都是自己。在查找一个元素的祖先节点时，如果该元素的祖先节点不是自己，则路径压缩，将该元素到祖先节点路径上的所有节点的祖先节点都设为祖先节点。在合并两个元素所在的集合时，将其中一个元素的祖先节点设为另一个元素的祖先节点即可。