【数据结构与算法】并查集模板

#include <vector>
using namespace std;

class UnionFind {
private:
    vector<int> parent;  // parent[i]：节点i的父节点
    // vector<int> rank;    // rank[i]：节点i所在树的“秩”（近似树高，用于按秩合并）

public:
    // 构造函数：初始化n个节点（节点编号建议从0或1开始，需与业务一致）
    explicit UnionFind(int n) {
        parent.resize(n);
        // rank.resize(n, 0);  // 初始时所有树的秩为0（单个节点）
        for (int i = 0; i < n; ++i) {
            parent[i] = i;  // 每个节点初始父节点是自身（独立成集）
        }
    }

    // 查找节点x所在连通集的根节点，并执行路径压缩（核心优化）
    int find(int x) {
        // 递归版：若x不是根节点，将x的父节点直接指向根节点（压缩路径）
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 递归找到根节点后，回溯更新x的父节点
        }
        return parent[x];  // 返回根节点

        // 迭代版（避免递归栈溢出，适合节点数极大的场景）
        // int root = x;
        // // 1. 先找到根节点
        // while (parent[root] != root) {
        //     root = parent[root];
        // }
        // // 2. 路径压缩：将x到根的所有节点父节点直接指向根
        // while (parent[x] != root) {
        //     int temp = parent[x];  // 暂存x的原父节点
        //     parent[x] = root;      // x的父节点指向根
        //     x = temp;              // 处理原父节点
        // }
        // return root;
    }

    // 合并节点x和y所在的连通集（按秩合并，核心优化）
    void unite(int x, int y) {
        int rootX = find(x);  // 先找到x的根
        int rootY = find(y);  // 先找到y的根

        if (rootX == rootY) {  // x和y已在同一连通集，无需合并
            return;
        }

        // 按秩合并：将秩小的树合并到秩大的树的根下（减少树的深度）
        /*
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;  // 根X的父节点设为根Y
        } else {
            parent[rootY] = rootX;  // 根Y的父节点设为根X
            if (rank[rootX] == rank[rootY]) {  // 若秩相等，合并后根X的秩+1
                rank[rootX]++;
            }
        }
        */
    }

    // 判断节点x和y是否在同一连通集（辅助接口）
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }

    // 统计连通集的个数（辅助接口）
    int getComponentCount() {
        int count = 0;
        int n = parent.size();
        for (int i = 0; i < n; ++i) {
            // 根节点的特征：parent[i] == i（需先find确保路径压缩完成）
            if (find(i) == i) {
                count++;
            }
        }
        return count;
    }
};