如何缩边双?
第一步,找出所有割边;
第二步,不经过割边遍历原图,每一个连通块即为一个边双。
如何找出割边同时缩点?
void Tarjan(int u, int edge){
dfn[u] = low[u] = ++cnt;
stk[++top] = u;
ins[u] = 1;
for(int e(fst[u]), v(ed[e].to); e; e = ed[e].nxt, v = ed[e].to){
if(!dfn[v]){
Tarjan(v, e);
low[u] = min(low[u], low[v]);
if(dfn[u] < low[v]) Brg[e] = Brg[e ^ 1] = 1;//v无法到达u及之前的点,即说明(u->v)是割边
}
else if(ins[v] && e != (edge ^ 1)){
low[u] = min(low[u], low[v]);
}
}
if(dfn[u] == low[u]){
bcc++;
do{
bl[stk[top]] = bcc;
W[bcc] += valstk[top];
ins[stk[top]] = 0;
}while(top && stk[top--] != u);
}
}