ABC75 C問題 - acchan’s blog

問題概要

自己ループと二重辺を含まない\(N\)頂点\(M\)辺の無向連結グラフが与えられる。
\(i\)番目の辺は頂点\(a_i\)と頂点\(b_i\)を結ぶ。
グラフから辺を取り除いた時、グラフ全体が火連結になるような辺のことを橋と呼ぶ時、橋の本数を求めよ。

制約

\(2 ≤ N ≤ 50\)
\(N-1 ≤ M ≤ min(N(N-1)/2, 50)\)
\(1 ≤ a_i < b_i ≤ N\)
与えられるグラフは自己ループと二重辺を含まない
与えられるグラフは連結である。

考えたこと

無向グラフのアルゴリズムには前回ABC54 C問題と同様に深さ優先探索を用いる(他にも幅優先探索、UnionFind, ワーシャル・フロイド法などが利用できるらしい)
dfsでは、N個の頂点それぞれに訪問したかどうかを調べる目的で使用する。

#include<bits/stdc++.h>
using namespace std;
const int ilmit=50;
bool graph[limit][limit];
bool visited[limit];
int n, m;
int a[limit], b[limit];

bool dfs(int v) {
  visited[v] = true;
  for(int v2 = 0; v2 < n; ++v2) {
    if(graph[v][v2] == false) continue; // そもそも辺がなければスキップ
    if(visited[v2]) continue;
    visited[v2] = true;
    dfs(v2);
  }
}

int main() {
  cin >> n >> m;
  for(int i = 0; i < m; ++i) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = true // グラフ上に辺があることを示す
  }
  
  int ans = 0;
  for(int i = 0; i < m; ++i) {
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = false; // 一つの辺を取り除く
    for(int j = 0; j < n; ++j) visited[j] = false; // どの頂点もまだ訪れていないということを表現
    dfs(0); // 頂点1から探索開始

    bool bridge = false;
    for(int j = 0; j < n; ++j) if(visited[j] == false) bridge = true;
    if(bridge) ans += 1;
  
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = true; // 取り除いた辺を復元
  }
  cout << ans << endl;

  return 0;
}