并查集

• 并查集用来表示各节点间的连通关系；
• 有些问题可以抽象用并查集来解决；
• 节点用数组表示！！！

基本

class UnionFind {
private:
    // 连接分量的数目
    int count;
    
    // 记录每个节点的父节点
    vector<int> parent;
public:
    UnionFind(int n) : count(n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    
    int Count() {
        return count;
    }
    
    // 找到该节点所在树的根节点
    int findRoot (int x) {
        while (x != parent[x]) {
            x = parent[x];
        }
        return x;
    }
    
    // 连接两个节点
    void unionIt(int p, int q) {
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if (rootP == rootQ) return;
        
        parent[rootP] = rootQ;
        --count;
    }
    
    // 确认两个节点是否连接
    bool isConnected(int p, int q) {
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        return rootP == rootQ;
    }
};

优化

class UnionFind {
private:
    // 连接分量的数目
    int count;
    // 记录每棵树的节点个数
    vector<int> size;
    // 记录每个节点的父节点
    vector<int> parent;
public:
    UnionFind(int n) : count(n) {
        parent.resize(n);
        size.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    int Count() {
        return count;
    }
    
    // 找到该节点所在树的根节点
    int findRoot (int x) {
        while (x != parent[x]) {
            // 路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    
    // 连接两个节点
    void unionIt(int p, int q) {
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if (rootP == rootQ) return;
        
        // 小树接在大树之下，更平衡
        if (size[rootP] >= size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        --count;
    }
    
    // 确认两个节点是否连接
    bool isConnected(int p, int q) {
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if (rootP == rootQ) return true;
        else return false;
    }
};