GRAPH_ - Tìm khớp và cầu (Cơ bản)
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <vector>
#include <cstdio>
#include <set>
using namespace std;
int n, m;
vector<pair<int,int> > ke[10010];
int num[10010], low[10010], fa[10010];
bool mark[10010], vsting[10010], khop[10010];
int tt = 0, sokhop, socau;
void dfs(int i, int edge) {
vsting[i] = true;
mark[i] = true;
num[i] = tt++;
low[i] = num[i];
int sc = 0;
for(int k=0;k<ke[i].size();++k) {
int j = ke[i][k].first;
if(!mark[j]) {
++sc;
fa[j] = i;
dfs(j, ke[i][k].second);
low[i] = min( low[i], low[j]);
}
else if(ke[i][k].second != edge && vsting[j])
low[i] = min( low[i], num[j]);
}
if(edge != -1 && low[i] == num[i]) ++socau;
if(edge == -1) {
if(sc > 1) khop[i] = true;
else khop[i] = false;
}
if(edge != -1 && low[i] >= num[fa[i]]) khop[fa[i]] = true;
vsting[i] = false;
}
int main() {
scanf("%d%d", &n, &m);
set<pair<int,int> > se;
for(int i=0;i<m;++i) {
int u, v;
scanf("%d%d", &u, &v);
if(!se.count(make_pair(u,v))) {
ke[u].push_back(make_pair(v,i));
ke[v].push_back(make_pair(u,i));
se.insert(make_pair(u,v));
se.insert(make_pair(v,u));
}
}
for(int i=1;i<=n;++i)
if(!mark[i]) {
dfs(i, -1);
}
for(int i=1;i<=n;++i) if(khop[i]) ++sokhop;
cout << sokhop << " " << socau << endl;
return 0;
}