c语言并查集的路径压缩的非递归实现

并查集是一种用于处理集合分治问题的数据结构，常用于图的连通性判断、元素归属等场景。在C语言中，路径压缩是优化并查集性能的一个常用技术，它减少了查找根节点时所需的平均时间。

非递归的并查集中，通常会维护每个集合的“秩”（rank）和代表该集合根节点的指针。以下是路径压缩的基本步骤：

1. 初始化阶段：给每个元素分配一个独立的根节点，秩设为0。

typedef struct {
    int root; // 根节点索引
    int rank; // 当前集合的秩（用于比较大小）
} DisjointSet;

2. 查找操作：如果当前元素不是其根节点，就沿着路径向上找到根，同时更新秩值，直到达到根节点。

int find(int id, DisjointSet* sets) {
    while (sets[id].root != id) { // 直到找到根
        id = sets[sets[id].root].root; // 路径压缩：设置id的根为根的根
    }
    return id;
}

3. 合并操作：合并两个集合时，首先找到两个集合的根，然后选择秩较大的那个作为新的根，并将较小根的秩加一（这样可以保持秩在合并后的大小），然后连接它们的成员。

void union_set(int a, int b, DisjointSet* sets) {
    int root_a = find(a, sets);
    int root_b = find(b, sets);

    if (sets[root_a].rank < sets[root_b].rank) {
        sets[root_a].root = root_b;
    } else if (sets[root_a].rank > sets[root_b].rank) {
        sets[root_b].root = root_a;
    } else { // 级别相同，提升较小集合的秩避免下次查找时需要继续压缩
        sets[root_a].root = root_b;
        sets[root_b].rank++;
    }
}