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;
}

Download