并查集合并操作详解：Union 函数代码解析

并查集合并操作详解：Union 函数代码解析

这段代码是实现并查集中的合并操作。并查集是一种数据结构，用于维护一个元素集合，支持查找和合并两个元素所在的集合。

void Union(UnionFindSet *set, int x, int y) {
    int xRoot = Find(set, x);
    int yRoot = Find(set, y);
    if (xRoot == yRoot) {
        return;
    }
    if (set->rank[xRoot] < set->rank[yRoot]) {
        set->parent[xRoot] = yRoot;
    } else if (set->rank[xRoot] > set->rank[yRoot]) {
        set->parent[yRoot] = xRoot;
    } else {
        set->parent[yRoot] = xRoot;
        set->rank[xRoot]++;
    }
}

代码解析：

1. 查找根节点： 使用 Find 函数分别找到元素 x 和 y 所在集合的根节点 xRoot 和 yRoot。
2. 判断是否已合并： 如果 xRoot 和 yRoot 相等，说明 x 和 y 已经在同一个集合中，不需要合并，直接返回。
3. 合并操作： 如果 x 和 y 不在同一个集合中，需要将它们所在的集合合并起来。
   • 维护秩 (rank)： 为了保证并查集的平衡性，需要维护每个节点的秩，即它们的深度。
   • 比较秩：
     • 如果 xRoot 的秩比 yRoot 小，将 xRoot 的父节点指向 yRoot，因为 yRoot 的深度更大。
     • 如果 xRoot 的秩比 yRoot 大，将 yRoot 的父节点指向 xRoot。
     • 如果它们的秩一样，可以任选一个节点作为新的根节点，并将它的秩加一，因为它的深度比原来的节点深了一层。

总结：

通过 Union 函数，我们可以将多个元素所在的集合合并成一个大集合，从而实现集合之间的合并。并查集中的 Find 和 Union 函数是其核心操作，通过这两个操作，可以实现集合的查找和合并。