关于求边双联通分量
  • 板块学术版
  • 楼主东灯
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/7/12 10:26
  • 上次更新2023/10/27 20:57:24
查看原帖
关于求边双联通分量
160363
东灯楼主2022/7/12 10:26

不同于求桥后用dfs不走桥走出边双

我今天看到了另外一种震撼我妈的边双的求法:

我第一时间的理解是:类似求SCC,这种方法在找最大简单环,然后利用“边双连通分量中任意一条边都包含在至少一个简单环中”求出边双,这种解释是否正确?

void tarjan(int x,int father){
	dfn[x]=low[x]=++nowtime;
	s.push(x);
	for(register int i=head[x];i;i=e[i].next){
		int v(e[i].to);
		if(!dfn[v]){
			tarjan(v,i);
			low[x]=Min(low[x],low[v]);
		}else if(i!=(father^1))low[x]=Min(low[x],dfn[v]);
	}
	if(dfn[x]==low[x]){
		++dcccnt;
		int k;
		do{
			k=s.pop();
			belong[k]=dcccnt;
		}while(k!=x);
	}
}
2022/7/12 10:26
加载中...