disjointset.cpp

// ============================================================
//                    并查集（Disjoint Set / Union-Find）
// ============================================================
//
// 【核心概念】
//   并查集用于高效管理"不相交集合"的合并与查询。
//   典型应用：判断图中两个节点是否连通、Kruskal 最小生成树等。
//
// 【两个核心操作】
//   find(x)：找到 x 所属集合的代表元素（根）。通过"路径压缩"
//            让每个节点直接指向根，大幅加速后续查找。
//
//   unionSets(x, y)：合并 x 和 y 所在的两个集合。通过"按大小
//                    合并"让较小的集合挂到较大集合的根下，控制树高。
//
// 【parent 数组的巧妙设计】
//   parent[i] < 0  → i 是根节点，|parent[i]| = 集合大小
//   parent[i] >= 0 → i 不是根，parent[i] = 父节点索引
//
//   一个数组同时存储了"父指针"和"集合大小"两个信息！
//
//   初始化：所有 parent[i] = -1（每个节点都是大小为 1 的独立集合）
//
//   示例（合并 0 和 1）：
//     parent = [-1, -1]        初始状态
//     union(0, 1):             两集合大小相同，将 0 挂到 1 下
//     parent = [1, -2]         1 是根（-2 表示大小 2），0 的父节点是 1
//
// 【路径压缩（find 中）】
//   parent[x] = find(parent[x]);
//   这一行让 x 直接指向根，将沿途的链"拍平"。
//   下次再找 x（及其子孙）时就是 O(1)。
//
//   示例：1→2→3→4（4 是根，parent = [? , 2, 3, 4, -4]）
//   执行 find(1) 后：1→4, 2→4, 3→4
//   路径被压缩，后续查找 1 只需一步。
//
// 【按大小合并（unionSets 中）】
//   比较两个根集合的大小（|parent[root]|），总是把小的挂到大的上。
//   这样树高不会超过 log n。
//
// 【时间复杂度】
//   使用了路径压缩 + 按大小合并后，均摊复杂度接近 O(α(n))，
//   其中 α 是反阿克曼函数——增长极慢，实际上可看作 O(1)。
//
// ============================================================

#include<iostream>
#include<vector>
using namespace std;

// 【阅读地图】
//   先看 parent 数组如何表示森林，再看 Find 的路径压缩和 Union 的按大小合并。
//   根节点的 parent 指向自身；同一集合中任意元素的 Find 结果必须相同。
//   路径压缩改变父指针但不改变集合划分，按大小合并限制树高增长，两者共同带来均摊效率。

class disjointset
{
private:
    // parent[i] < 0  → i 是根，|parent[i]| = 集合大小
    // parent[i] >= 0 → parent[i] 是 i 的父节点索引
    vector<int> parent;

public:
    // ----------------------------------------------------------
    // 构造函数：初始化 size 个独立集合
    //
    // 目的：创建并查集，初始时每个元素都是独立的集合。
    // 操作：将 parent 数组全部初始化为 -1，
    //      表示每个元素都是大小为 1 的根节点。
    //
    // 为什么要用 -1？负数既标记"是根"又存储"集合大小"，
    // 一个数组承担两个职责。
    // ----------------------------------------------------------
    disjointset(int size)
    {
        parent.assign(size, -1);
    }

    // ----------------------------------------------------------
    // find(x)：查找元素 x 所属集合的根，同时进行路径压缩
    //
    // 目的：确定 x 属于哪个集合。两个元素同一集合 ↔ find 返回相同根。
    //
    // 路径压缩：查找过程中，将沿途所有节点直接挂到根上。
    // 这样做之后，下次再查找这些节点就是 O(1)。
    //
    // 递归写法等价于：
    //   if (parent[x] >= 0)
    //       parent[x] = find(parent[x]);  // 直接指向根
    //   return parent[x] < 0 ? x : parent[x];
    //
    // 为什么路径压缩不影响正确性？
    //   压缩只改变树的结构（更扁平），不改变连通关系。
    //   同一个集合的节点始终在同一个根下。
    //
    // 示例：1→2→3→4（4 是根）
    //   执行 find(1) 后：1→4, 2→4, 3→4（链被"拍平"）
    // ----------------------------------------------------------
    int find(int x)
    {
        if (parent[x] < 0)
        {
            return x;  // x 就是根
        }
        else
        {
            parent[x] = find(parent[x]);  // 路径压缩：直接连到根
            return parent[x];
        }
    }

    // ----------------------------------------------------------
    // unionSets(x, y)：合并 x 和 y 所在的两个集合（按大小合并）
    //
    // 目的：将两个不相交的集合合并为一个。如果已在同一集合，什么都不做。
    //
    // 按大小合并策略：
    //   总是将"较小的集合"挂到"较大集合"的根下。
    //   这样树高增长最慢——因为小集合挂到大集合下面，
    //   不会增加已有大部分节点的深度。
    //
    // parent[root] 存储的是负数，表示取反后是集合大小。
    // parent[root1] < parent[root2]（如 -5 < -3）
    //   → |parent[root1]| > |parent[root2]|
    //   → root1 的集合更大 → root2 挂到 root1 下
    //
    // 执行步骤：
    //   ① find(x) 和 find(y) 获取各自的根
    //   ② 如果根相同 → 已经同一集合，直接返回
    //   ③ 比较集合大小，将小的根指向大的根
    //   ④ 更新大根的大小 = 两集合大小之和
    //
    // 示例：
    //   root1（大小 5）：parent[root1] = -5
    //   root2（大小 3）：parent[root2] = -3
    //   -5 < -3 → root1 更大
    //   parent[root1] = -5 + (-3) = -8  （合并后大小 = 8）
    //   parent[root2] = root1            （root2 指向 root1）
    // ----------------------------------------------------------
    void unionSets(int x, int y)
    {
        int root1 = find(x);
        int root2 = find(y);

        if (root1 == root2) return;  // 已经在同一集合

        // 比较大小：parent 存的是负数，越小 → 集合越大
        if (parent[root1] < parent[root2])
        {
            // root1 集合更大 → root2 挂到 root1 下
            parent[root1] += parent[root2];  // 更新大小（负数相加）
            parent[root2] = root1;           // root2 指向新父节点
        }
        else
        {
            // root2 集合更大或相等 → root1 挂到 root2 下
            parent[root2] += parent[root1];
            parent[root1] = root2;
        }
    }

    // ----------------------------------------------------------
    // setSize(x)：获取元素 x 所在集合的大小
    //
    // 目的：查询 x 所在集合有多少个元素。
    // 操作：find(x) 找到根，根的 |parent| 就是集合大小。
    //
    // 典型应用：判断连通分量大小、Kruskal 算法中检查是否已连接所有顶点。
    // ----------------------------------------------------------
    int setSize(int x)
    {
        return -parent[find(x)];  // 根节点的 parent 存的是 -size
    }
};

// ============================================================
//                         测 试 主 函 数
// ============================================================

int main()
{
    cout << "╔══════════════════════════════════╗" << endl;
    cout << "║    并 查 集 测 试                ║" << endl;
    cout << "╚══════════════════════════════════╝" << endl;

    disjointset ds(10);

    // 初始状态：每个节点独立
    cout << "\n┌─ 初始状态 ─────────────────────┐" << endl;
    cout << "find(0)=" << ds.find(0) << ", find(5)=" << ds.find(5) << " (各自独立)" << endl;
    cout << "find(0)==find(5) → " << (ds.find(0) == ds.find(5)) << " (expect 0)" << endl;

    // 合并操作
    cout << "\n┌─ 合并操作 ─────────────────────┐" << endl;
    ds.unionSets(0, 1);
    ds.unionSets(0, 2);
    ds.unionSets(3, 4);
    ds.unionSets(0, 3);  // 两个集合合并
    cout << "合并 0-1-2-3-4 后: find(0)==find(4) → " << (ds.find(0) == ds.find(4)) << " (expect 1)" << endl;
    cout << "find(0)==find(5) → " << (ds.find(0) == ds.find(5)) << " (expect 0)" << endl;
    cout << "集合0的大小=" << ds.setSize(0) << " (expect 5)" << endl;

    // 路径压缩效果
    cout << "\n┌─ 路径压缩 ─────────────────────┐" << endl;
    ds.unionSets(5, 6);
    ds.unionSets(6, 7);
    ds.unionSets(5, 0);  // 大合并
    cout << "全合并后: find(1)==find(7) → " << (ds.find(1) == ds.find(7)) << " (expect 1)" << endl;
    cout << "总元素数: setSize(0)=" << ds.setSize(0) << " (expect 8)" << endl;

    cout << "\n所有测试完成！" << endl;
    return 0;
}