Bridge [AtCoder Beginner Contest 075 C]

https://beta.atcoder.jp/contests/abc075/tasks/abc075_c

前提知識

• UnionFind

解法

https://beta.atcoder.jp/contests/abc075/submissions/1682311

全ての辺について橋となるかを確かめる。
辺iが橋かどうかは辺i以外の辺を使うとグラフ全体が連結かどうかを判定すればいい。
これにはUnionFindを使おう。
辺i以外の辺を使ってUnionFindで連結する。
もし、グラフ全体が連結ならばuf[i]=iとなる頂点がただ1つだけある。
そうでなければ非連結なので、uf[i]=iとなる頂点を数えて判定すればいい。

int N, M;
int A[101], B[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> A[i] >> B[i], A[i]--, B[i]--;
 
    int ans = 0;
    rep(i, 0, M) {
        UnionFind uf(N);
        rep(j, 0, M) if (j != i) uf(A[j], B[j]);
        int c = 0;
        rep(j, 0, N) if (j == uf[j]) c++;
        if (1 < c) ans++;
    }
    cout << ans << endl;
}