并查集

实现

包括路径压缩与按秩合并

class UnionFind {
public:
    UnionFind(int n) {
        f.assign(n + 1, 0);
        rank.assign(n + 1, 1);

        for(int i = 0; i <= n; i++) {
            f[i] = i;
        }
    }

    int find(int x) {
        return x == f[x] ? x : (f[x] = find(f[x]));
    }

    // 函数名不能用union，会与c++关键字冲突
    void merge(int a, int b) {
        int x = find(a), y = find(b);
        if(rank[x] <= rank[y]) {
            f[x] = y;
        } else {
            f[y] = x;
        }
        if(rank[x] == rank[y] && x != y) {
            rank[y]++;
        }
    }

    bool connected(int a, int b) {
        int roota = find(a), rootb = find(b);
        return roota == rootb;
    }

private:
    vector<int> f, rank;
};

实现

相关题目

参考