素集合データ構造と Union-Find アルゴリズム

素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。

Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。

Union: 2つの集合を1つに統合する。

これら2つの操作をサポートしているため、素集合データ構造は「Union-Findデータ構造」あるいは「Merge-Find集合」とも呼ばれる。これら以外の重要な操作として MakeSetがある。これは、与えられた1つの要素だけを格納した集合（シングルトン）を作成する。これら3つの操作により、様々な実用的分割問題を解くことができる（「応用」の節を参照）。

素集合データ構造 - Wikipedia

と，いうわけで実装

class DisjointSet {
private:
    vector<unsigned> par;    // par[x] : x の親ノード
    vector<unsigned> rank;   // rank[x] : 木の高さ
    size_t sz;             // 集合の個数
public:

    // コンストラクタ : 空
    DisjointSet() : sz(0) { }

    // コンストラクタ : 1 要素の集合 n 個
    DisjointSet(size_t n) :
        par(n, -1), rank(n, 0), sz(n) {
        for (size_t i = 0; i < n; i++) par[i] = i;
    }

    size_t size() { return sz; }

    // 集合の追加 : 1 個
    void makeset() {
        par.push_back(par.size());
        rank.push_back(0);
        sz++;
    }
    // 集合の追加 : n 個
    void makeset(size_t n) {
        for (size_t i = 0; i < n; i++) makeset();
    }

    // x が属する集合の代表元を返す
    size_t find(size_t x) {
        if (par[x] == x)
            return x;
        else
            return par[x] = find(par[x]);
    }

    // x が属する集合と y が属する集合をマージする
    void unite(size_t x, size_t y) {
        x = find(x);
        y = find(y);
        if (x == y) return;

        if (rank[x] < rank[y])
            par[x] = y;
        else {
            par[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
        sz--;
    }

    // x と y が同じ集合に属しているか？
    bool same(size_t x, size_t y) {
        return find(x) == find(y);
    }
};

蟻本との差異として素集合のサイズを求めることができるようにしてある (マージしたら -1 すればいいだけ)．

これを使うと先週の ABC075 の C 問題とかがえらく楽になる．

元のコード

typedef pair<int, int> edge;
vector<edge> edges;
 
int problemC()
{
    int N, M, ans = 0;
    cin >> N >> M;
 
    int v, w;
    for (int i = 0; i < M; i++) {
        cin >> v >> w;
        edges.push_back(edge(v, w));
    }
 
    // i : off にする辺
    for (int i = 0; i < M; i++) {
 
        vector<vector<int> > li(N + 1);
        // 辺 i を除いて隣接リストを作る
        for (int j = 0; j < M; j++) {
            if (j == i) continue;
            edge e = edges[j];
            li[e.first].push_back(e.second);
            li[e.second].push_back(e.first);
        }
 
        queue<int> qu;
        set<int> st;
 
        qu.push(1);
 
        // 頂点 1 とつながっている頂点の個数を数える
        while (!qu.empty()) {
            int v = qu.front();
            qu.pop();
            st.insert(v);
 
            for (int k = 0; k < li[v].size(); k++) {
                if (st.find(li[v][k]) == st.end()) qu.push(li[v][k]);
            }
        }
 
        // N でなければ連結成分が複数ある
        if (st.size() != N) ans++;
    }
 
    cout << ans << endl;
 
    return 0;
}

Union-Find バージョン

typedef pair<int, int> edge;

int problemC()
{
    int N, M;
    cin >> N >> M;

    int a, b;
    vector<edge> edges;

    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        edges.push_back(edge(a - 1, b - 1)); // 0-based に変換
    }

    int ans = 0;
    // i : off にする辺
    for (int i = 0; i < M; i++) {
        DisjointSet ds(N);
        for (int j = 0; j < M; j++) {
            if (i == j) continue;
            ds.unite(edges[j].first, edges[j].second);
        }
        if (ds.size() != 1) ans++;
    }

    cout << ans << endl;

    return 0;
}

超スッキリ

絶滅

どうでもいい

素集合データ構造と Union-Find アルゴリズム