GRAPH_ - Tìm khớp và cầu (Cơ bản)
Tác giả: skyvn97
Ngôn ngữ: C++
#include<set>
#include<cstdio>
#include<vector>
#include<cstring>
#define MAX 10101
using namespace std;
typedef pair<int,int> ii;
vector<int> g[MAX];
set<ii> bl;
int m,n;
int low[MAX];
int num[MAX];
int nch[MAX];
bool cutv[MAX];
int cnt;
int nb,nc;
void loadgraph(void) {
scanf("%d",&n);
scanf("%d",&m);
int i,u,v;
for (i=1;i<=n;i=i+1) g[i].clear();
for (i=1;i<=m;i=i+1) {
scanf("%d",&u);
scanf("%d",&v);
g[u].push_back(v);
g[v].push_back(u);
}
}
int min(const int &x,const int &y) {
if (x<y) return (x); else return (y);
}
void visit_bridge(const int &u) {
int i,v;
cnt++;
num[u]=cnt;
low[u]=n+1;
for (i=0;i<g[u].size();i=i+1) {
v=g[u][i];
if (bl.find(ii(u,v))!=bl.end()) continue;
bl.insert(ii(v,u));
if (num[v]==0) {
visit_bridge(v);
if (low[v]>num[u]) nb++;
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],num[v]);
}
}
void count_bridge(void) {
memset(low,0,sizeof low);
memset(num,0,sizeof num);
bl.clear();
nb=0;
cnt=0;
int i;
for (i=1;i<=n;i=i+1)
if (num[i]==0) visit_bridge(i);
printf("%d",nb);
}
void visit_cutvert(const int &u) {
int i,v;
cnt++;
num[u]=cnt;
low[u]=n+1;
cutv[u]=false;
for (i=0;i<g[u].size();i=i+1) {
v=g[u][i];
if (num[v]==0) {
nch[u]++;
visit_cutvert(v);
cutv[u]=cutv[u]||(low[v]>=num[u]);
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],num[v]);
}
}
void count_cutvert(void) {
memset(low,0,sizeof low);
memset(num,0,sizeof num);
memset(nch,0,sizeof nch);
nc=0;
cnt=0;
int i;
for (i=1;i<=n;i=i+1) {
if (num[i]==0) {
visit_cutvert(i);
if (nch[i]<2) cutv[i]=false;
}
}
for (i=1;i<=n;i=i+1) nc+=cutv[i];
printf("%d ",nc);
}
int main(void) {
loadgraph();
count_cutvert();
count_bridge();
return 0;
}