模板-并查集

模板-并查集

模板

struct disjoint_set {

    std::vector<int> s, sz;

    disjoint_set() = default;
    disjoint_set(size_t size) : s(size + 1, 0), sz(size + 1, 1) {
        std::iota(s.begin(), s.end(), 0); // <numeric>
    }

    int find(int x) {
        return x == s[x] ? x : s[x] = find(s[x]); // 路径压缩
    }

    bool unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return true; // 已经联通返回 true;
        if(sz[x] > sz[y])
            std::swap(x, y);
        sz[y] += sz[x];   // 按秩合并
        s[x] = y;
        return false; 
    }
};