首页 > 代码库 > Tarjan 算法求无向图的割顶和桥

Tarjan 算法求无向图的割顶和桥

#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int N = 250;int head[N], low[N], dfn[N], fa[N];int n, m, now = 1, Tarjan_clock;bool is_cut[N];struct Node{	int u, v, nxt;}E[N];inline int read(){	int x = 0; char c = getchar();	while(c < ‘0‘ || c > ‘9‘) c = getchar();	while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = getchar();	return x;}inline void add(int u, int v){	E[now].v = v;	E[now].nxt = head[u];	head[u] = now ++;}void Tarjan(int x, int fa_x){	low[x] = dfn[x] = ++ Tarjan_clock;	fa[x] = fa_x;	for(int i = head[x]; ~ i; i = E[i].nxt)	{		int v = E[i].v;		if(!dfn[v])		{			Tarjan(v, x);			low[x] = min(low[x], low[v]);		}		else			if(v != fa_x)				low[x] = min(low[x], dfn[v]);	}}inline void August_13th(){	int root_son = 0;	Tarjan(1, 0);	for(int i = 2; i <= n; i ++)	{		int fa_i = fa[i];		if(fa_i == 1)			root_son ++;		else 			if(low[i] >= dfn[fa_i])				is_cut[fa_i] = 1;	}	if(root_son > 1)		is_cut[1] = 1;	for(int i = 1; i <= n; i ++)		if(is_cut[i])			printf("%d\n", i);	for(int i = 1; i <= n; i ++)	{		int fa_i = fa[i];		if(fa_i > 0 && low[i] > dfn[fa_i])			printf("%d,%d\n",fa_i,i);	}}int main(){	n = read();	m = read();	for(int i = 1; i <= n; i ++)		head[i] = -1;	for(int i = 1; i <= m; i ++)	{		int u = read();		int v = read();		add(u, v);		add(v, u);	}	August_13th();			return 0;}

  

Tarjan 算法求无向图的割顶和桥