如何缩边双

如何缩边双?

第一步,找出所有割边;
第二步,不经过割边遍历原图,每一个连通块即为一个边双。

如何找出割边同时缩点?

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);
	}
}
上一篇:leetcode 二叉树的中序遍历(递归与非递归) 简单


下一篇:【经典算法题】最长有效括号