不同于求桥后用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);
}
}