AtCoder ABC 075 C - Bridge (緑色, 300 点)

Union-Find や、DFS、BFS などで解ける問題ですね。

• 問題へのリンク

問題概要

頂点数 、辺数 の連結な単純無向グラフ が与えられます。

グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。

グラフ において、橋が何本あるかを求めてください。

制約

• 
• 

方針

が十分小さいので、次のような愚直な方針でも十分解くことができます。

---

1. グラフ の各辺 に対して、 から辺 を除去したグラフ を生成する。

2. そして、グラフ が連結かどうかを判定する

---

1 については、グラフ の構造体を作ってから辺 を削除するのは大変です。そこで、次のようにするのが楽でしょう。

「各辺 ごとに、 から辺 を除いた 本の辺からなるグラフを毎回新たに構築する」

このようにしたグラフ が連結かどうかを判定します。ここでは Union-Find を用いた解を示します。DFS による解は公式解説にあります。

Union-Find を用いた場合、計算量は となります。

コード

#include <iostream>
#include <vector>
using namespace std;

// Union-Find
struct UnionFind {
    vector<int> par;

    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    // 入力
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    for (int i = 0; i < M; ++i) {
        cin >> A[i] >> B[i];
        --A[i], --B[i];
    }

    // 各辺を除外して Union-Find で判定
    int res = 0;
    for (int e = 0; e < M; ++e) {
        UnionFind uf(N);
        for (int i = 0; i < M; ++i) {
            // 辺 e を除外
            if (i == e) continue;

            uf.merge(A[i], B[i]);
        }

        // 連結成分の個数を求める
        int num = 0;
        for (int v = 0; v < N; ++v) {
            if (uf.root(v) == v) ++num;
        }

        // 連結成分数が 1 より大きいと非連結
        if (num > 1) ++res;
    }       
    cout << res << endl;
}