并查集 (Union-Find) 可视化教学

并查集将每个集合表示为一棵树。集合中的每个元素都是树上的一个节点。我们使用一个 `parent` 数组来存储这种父子关系：`parent[i]` 存储节点 `i` 的父节点。

树的根节点比较特殊，它的父节点是它自己，即 `parent[root] == root`。这个根节点作为整个集合的唯一“代表”。

初始化 (Initialize)：开始时，每个元素都是一棵只有一个节点的树（即根节点），所以 `parent[i] = i` 对所有元素 `i` 成立。

查找 (Find)：要找到元素 `x` 所属集合的代表，我们从 `x` 开始，沿着 `parent` 指针不断向上查找，直到找到一个节点 `p` 满足 `parent[p] == p`。这个节点 `p` 就是集合的根（代表）。

基本的 Find 操作是递归或迭代地沿着父指针向上查找，直到找到根节点。

朴素 Find 实现 (C++):

int find(int i) {
    while (parent[i] != i) {
        i = parent[i]; // 不断向上移动
    }
    return i; // 返回根节点
}

这种朴素实现的缺点是，如果树退化成一条长链，Find 操作的时间复杂度可能达到 O(N)，其中 N 是元素总数。

路径压缩是 Find 操作的一个强大优化。它的思想是：在从某个节点 `x` 向上查找到根节点 `root` 的过程中，将这条路径上的所有节点的 `parent` 指针直接指向 `root`。

这样做的好处是“压平”了树的结构，使得下次再查找这些节点或其子节点时，能够更快地到达根节点。

带路径压缩的 Find 实现 (C++ - 递归):

int find(int i) {
    if (parent[i] == i) {
        return i; // 找到根节点
    }
    // 递归查找根节点，并将当前节点的父指针直接指向根节点
    parent[i] = find(parent[i]);
    return parent[i];
}

路径压缩显著降低了 Find 操作的摊销时间复杂度。

Union 操作用于合并包含元素 `x` 和元素 `y` 的两个集合。步骤如下：

1. 使用 Find 操作分别找到 `x` 和 `y` 的根节点，记为 `rootX` 和 `rootY`。
2. 如果 `rootX` 和 `rootY` 相同，说明 `x` 和 `y` 已经在同一个集合中，无需操作。
3. 如果 `rootX` 和 `rootY` 不同，将其中一个根节点（例如 `rootY`）的 `parent` 指针指向另一个根节点（例如 `rootX`），即 `parent[rootY] = rootX`。这样就将两棵树合并成了一棵。

朴素 Union 实现 (C++):

void unite(int x, int y) {
    int rootX = find(x); // 查找 x 的根
    int rootY = find(y); // 查找 y 的根
    if (rootX != rootY) {
        parent[rootY] = rootX; // 将 y 所在树合并到 x 所在树
    }
}

朴素的 Union 操作也可能导致树结构不平衡，形成长链。

按秩合并（或按大小合并）是 Union 操作的优化策略，目的是保持树的平衡，避免出现过高的树。

• 按秩 (Rank)：为每个根节点维护一个“秩”（大致表示树的高度）。合并时，总是将秩较小的树的根节点连接到秩较大的树的根节点上。如果两树秩相同，任选一个根作为新根，并将新根的秩加 1。
• 按大小 (Size)：为每个根节点维护其所在集合的大小（节点数量）。合并时，总是将规模较小的集合的根节点连接到规模较大的集合的根节点上，并更新新根的大小。

这两种策略都能有效控制树的高度或规模，防止退化。

带按秩合并的 Union 实现 (C++): (需要额外 `rank` 数组)

// 假设 rank[i] 初始化为 0
void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        // 按秩合并
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY; // X 树接到 Y 树
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX; // Y 树接到 X 树
        } else {
            parent[rootY] = rootX; // 秩相同，Y 接到 X
            rank[rootX]++;       // X 树的秩增加 1
        }
    }
}

单独使用路径压缩或按秩合并，都能显著改善性能。

当 **同时使用路径压缩和按秩（或大小）合并** 时，并查集的操作达到极其优异的性能：

对于 m 次操作（Find 或 Union）和 n 个元素：

• 总时间复杂度接近 O(m * α(n))，其中 α(n) 是反阿克曼函数 (Inverse Ackermann function)。
• α(n) 的增长极其缓慢，对于所有实际可能的 n 值（例如宇宙中的原子数），α(n) 的值不会超过 5。
• 因此，在实际应用中，每次操作的 **摊销时间复杂度可以认为接近 O(1)**，即近乎常数时间！

这就是并查集如此高效和受欢迎的原因。

Kruskal 算法是计算图的最小生成树 (MST) 的经典算法之一。其基本思想是：

1. 将图中所有的边按权重从小到大排序。
2. 初始化一个并查集，图中的每个顶点自成一个集合。
3. 依次遍历排序后的边 (u, v)：
   • 使用 Find 操作检查顶点 u 和顶点 v 是否属于同一个集合（即它们的根节点是否相同）。
   • 如果它们 **不** 属于同一个集合，说明加入这条边不会形成环路。将这条边加入 MST，并使用 Union 操作合并 u 和 v 所在的集合。
   • 如果它们 **属于** 同一个集合，说明加入这条边会形成环路，则跳过这条边。
4. 当加入的边数达到 N-1（N 为顶点数）时，算法结束，MST 构建完成。

并查集在这里的作用就是高效地检测环路（通过 Find 判断连通性）和合并连通分量（通过 Union）。