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

Download