ABC075: C - Bridge
問題
C: Bridge - AtCoder Beginner Contest 075 | AtCoder
解答
が小さい。のループで橋を一つずつ使用不可にして、あるノードから全てのノードに到達可能かをDFSで調べれば良い。で解ける。
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"; }