ABC075: C - Bridge

問題

C: Bridge - AtCoder Beginner Contest 075 | AtCoder

解答

N, Mが小さい。Mのループで橋を一つずつ使用不可にして、あるノードから全てのノードに到達可能かをDFSで調べれば良い。O(MN)で解ける。

vector<vector<int>> G;
vector<pair<int, int>> es;
set<int> wvis;

void dfs(int curr, set<int>& vis, int unuse) {
  rep(i, G[curr].size()) {
    int next = G[curr][i];
    if (es[unuse].first == curr && es[unuse].second == next) { continue; }
    if (es[unuse].first == next && es[unuse].second == curr) { continue; }
    if (vis.count(next)) { continue; }
    vis.insert(next);
    wvis.insert(next);
    dfs(next, vis, unuse);
    vis.erase(next);
  }
}

int main() {
  int N; cin >> N;
  int M; cin >> M;
  G.resize(N);
  rep(i, M) {
    int a, b; cin >> a >> b;
    a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
    es.emplace_back(a, b);
  }

  int ans = 0;
  rep(i, M) {
    set<int> vis;
    wvis.clear();
    vis.insert(0);
    wvis.insert(0);
    dfs(0, vis, i);
    ans += wvis.size() != N;
  }

  cout << ans << "\n";
}