首页 > 代码库 > 【连通图】双连通模板 Tarjan
【连通图】双连通模板 Tarjan
比起求无向图关节点的算法,只是多了一个栈,用来储存不存在关节点的所有边,遇到关节点之后弹出所有边进行储存
int dfs(int u, int fa) { int lowu = dfn[u] = ++deep; int son = 0; for(int i = head[u]; ~i; i = e[i].next) { int v = e[i].v; Pair p = Pair(u, v); if(!dfn[v]) { s.push(p); son++; int lowv = dfs(v, u); lowu = min(lowu, lowv); if(lowv >= dfn[u]) { iscut[u] = 1; bcc_cnt++;//从1开始编号的 bcc[bcc_cnt].clear(); while(1) { Pair x = s.top(); s.pop(); if(bcc_id[x.u] != bcc_cnt) { bcc[bcc_cnt].PB(x.u); bcc_id[x.u] = bcc_cnt; } if(bcc_id[x.v] != bcc_cnt) { bcc[bcc_cnt].PB(x.v); bcc_id[x.v] = bcc_cnt; } if(x.u == u && x.v == v) break; }//弹出所有边进行储存,直到遇见了u->v } } else if(dfn[v] < dfn[u] && v != fa) { s.push(p); lowu = min(lowu, dfn[v]); } } if(fa == -1 && son == 1) iscut[u] = 0; return lowu; }
如果图不连通,还要加上这个:
for(int i = 0; i< n; i++) { if(!dfn[i]) dfs(i, -1); }//为每个连通图跑一次tarjan
【连通图】双连通模板 Tarjan
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。