学习笔记——双连通分量

前言

我们的神，MC 曾经曰过，Tarjan 是 \(11\) 级算法。

边双

桥： 在一张连通无向图中，如果去掉一条边使得图的极大连通分量增加了，那么这条边就叫做桥。
边双连通分量： 一张无向图中的一个极大连通子图不存在桥，那么这个子图就是边双（e-bcc）。

性质： 一张无向图进行边双缩点之后是一棵树。

求桥

直接记录 dfn 和 low，意义和 Tarjan 缩点相同。但是不用记录栈。遍历儿子的时候判断是否有 low[s]>dfn[x]，如果是，说明儿子无法到达当前节点的祖先，也就是当前边是桥。对边记录编号后打标记即可。

void Tarjan(int x,int fa){
	dfn[x]=low[x]=++tot;
	for(pii s:g[x]){
		if(s.fi==fa) continue;
		if(!dfn[s.fi]){
			Tarjan(s.fi,x);
			low[x]=min(low[x],low[s.fi]);
			if(dfn[x]<low[s.fi]) vis[s.se]=vis[s.se^1]=1;
		}else low[x]=min(low[x],dfn[s.fi]);
	}
}

求 e-bcc

方法一： 用上面的方法求出所有的桥，然后去掉桥后每一个极大连通图就是一个 e-bcc。

void dfs(int x){
	col[x]=bcc;
	for(pii s:g[x]){
		if(vis[s.se]) continue;
		if(col[s.fi]) continue;
		dfs(s.fi);
	}
}

方法二： 也可以用 Tarjan 直接求 e-bcc。同样记录一个栈，在同一个 e-bcc 的点仍然会在一起。然后和普通的缩点没有很大区别。注意需要处理重边，因为两个点之间如果有重边，这两个点也属于同一个 e-bcc。我们直接在做的时候记录父亲，然后看儿子中父亲出现了几次，第一次出现的时候 continue，之后再出现说明是重边。

void Tarjan(int x,int fa){
	dfn[x]=low[x]=++tot;stk[++top]=x;
	bool flag=0;
	for(int s:g[x]){
		if(s==fa&&!flag){flag=1;continue;}
		if(!dfn[s]) Tarjan(s,x),low[x]=min(low[x],low[s]);
		else if(!col[s]) low[x]=min(low[x],dfn[s]);
	}if(dfn[x]==low[x]){
		bcc++;do{
			col[stk[top]]=bcc;
		}while(stk[top--]!=x);
	}
}

点双

割点： 在一张无向图中，去掉一个点和这个点所连接的边，极大连通分量增加，那么这个点是割点。
点双连通分量： 无向图中的一个极大连通子图，如果它没有割点，那么它就是一个点双连通分量（p-bcc）。

性质： 割点会同属于两个 p-bcc，所以在题目中我们一般采用圆方树来把点双问题转化为树上问题。

求割点

同样维护 dfn 和 low，如果 dfn[x]<=low[s]，说明 \(s\) 不能跨越 \(x\) 到前面的点去，则 \(x\) 是一个割点。

需要注意，对于根节点而言，没有办法用这种方式判断它是否是割点，但是我们可以看它为根的 dfs 生成树上有几条相连的树枝边，如果有 \(2\) 条以上与它相连的树枝边，那么根就是一个割点。

void Tarjan(int x,int fa){
	dfn[x]=low[x]=++tot;
	int cnt=0;
	for(int s:e[x]){
		if(!dfn[s]){
			cnt++;Tarjan(s,x);
			low[x]=min(low[x],low[s]);
			if(x!=fa&&low[s]>=dfn[x])
				ans[x]=1;
		}else if(s!=fa)
			low[x]=min(low[x],dfn[s]);
	}if(x==fa&&cnt>=2)
		ans[x]=1;
}

求 p-bcc

我们注意到一个割点属于两个不同的 p-bcc，所以用删去点后求连通图的方法行不通，所以只能采用 Tarjan 来做。

其实也很简单，只要在求割点的时候，维护一个栈就行了。

void Tarjan(int x,int fa){
	dfn[x]=low[x]=++tot;
	stk[++top]=x;
	for(int s:e[x]){
		if(!dfn[s]){
			Tarjan(s,x);
			low[x]=min(low[x],low[s]);
			if(low[s]>=dfn[x]){
				cnt++;
				while(stk[top]!=s)
					bcc[cnt].push_back(stk[top--]);
				bcc[cnt].push_back(stk[top--]);
				bcc[cnt].push_back(x);
			}
		}else low[x]=min(low[x],dfn[s]);
	}
}

简单感性理解一下为什么不需要特判根。首先如果根是割点，那么肯定是最后一个点一个 p-bcc。否则它应当会在某一个儿子的时候，从那个割点开始弹栈，然后直到弹到根。

维护 vector 是方便建树和其它操作。

后记

我们的神，MC 曾经曰过 Tarjan，是 \(11\) 级算法。
真的是 \(11\) 级吗，确定不用更高一点？