首页 > 代码库 > 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 算法求无向图的割顶和桥
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。