算法
(tarjan算法) $O(n+m)$
本题除了可以根据桥边的定义解决以外,还可以用 $\operatorname{tarjan}$ 算法解决。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
int ans = 0;
vector<int> ord(n, -1);
vector<int> low(n, -1);
int id = 0;
function<void(int, int)> tarjan = [&](int v, int p) {
ord[v] = low[v] = id++;
for (int u : to[v]) {
if (u == p) continue;
if (ord[u] == -1) {
tarjan(u, v);
low[v] = min(low[v], low[u]);
if (ord[v] < low[u]) {
ans++;
}
}
else {
low[v] = min(low[v], ord[u]);
}
}
};
rep(i, n) {
if (ord[i] == -1) tarjan(i, -1);
}
cout << ans << '\n';
return 0;
}