GRAPH_ - Tìm khớp và cầu (Cơ bản)
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<vector>
using namespace std;
const int N = 10005;
int n, m, cut, bridge, t, d[N], low[N];
vector<vector<int> > g;
void enter() {
scanf("%d%d",&n,&m); g.resize(n);
for(int i = 0; i < m; ++i) {
int u, v; scanf("%d%d",&u,&v);
g[--u].push_back(--v);
g[v].push_back(u);
}
}
void dfs(int u, int p) {
low[u] = d[u] = ++t; int iscut = 0, nchild = 0;
for(vector<int>::iterator v = g[u].begin(); v != g[u].end(); ++v)
if(d[*v] == 0) {
++nchild; dfs(*v, u); low[u] = min(low[u], low[*v]);
if(low[*v] >= d[u] && p != -1 || nchild == 2 && p == -1) iscut = 1;
if(low[*v] >= d[*v]) ++bridge;
} else if(*v != p) low[u] = min(low[u], d[*v]);
cut += iscut;
}
void solve() {
for(int u = 0; u < n; ++u) if(d[u] == 0) dfs(u, -1);
printf("%d %d\n", cut, bridge);
}
int main() {
enter();
solve();
return 0;
}