• 前言
• 无向图
  • 割点
  • 点双连通分量
  • 桥
  • 边双连通分量

前言

之前每次需要计算强连通分量的时候都用的 \(\text{Kosaraju}\)，主要是感觉 \(\rm Tarjan\) 好玄学，我的智商驾驭不了这个玩意儿。

但是，\(\rm Tarjan\) 真的太强大了！随便做道图论都有它！于是只有重学一遍，我真的是被逼的。

无向图

割点

先上代码吧：

for(int i=1;i<=n;++i)
    if(!dfn[i]) tarjan(i,i);

void tarjan(int u,int fa) {
	dfn[u]=low[u]=++idx;
	int son=0;
	for(int i=0;i<e[u].size();++i) {
		int v=e[u][i];
		if(v==fa) continue;
		if(!dfn[v]) {
			++son;
			tarjan(v,u);
			if((u^fa) and low[v]>=dfn[u])
				cut[u]=1;
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(u==fa and son>1) cut[u]=1;
}

定义 \(\text{dfn}_u\) 是遍历 \(u\) 的时间戳，\(\text{low}_u\) 是 \(u\) 在 不经过父亲 时能到达的时间戳最小的点的时间戳，初始时 \(\text{low}_u=\text{dfn}_u\)。我们先构建出一棵 \(\rm dfs\) 树，由于边是双向的，容易发现边只有树边与返祖边。这也是循环中的 if-else 判断。

那么当 \(u\) 通过树边连接到 \(v\) 时，如果 \(\text{low}_v\ge \text{dfn}_u\)，就说明 \(v\) 子树中没有点可以不经过 \(u\) 到达上层，所以 \(u\) 是割点。需要注意的是，每个连通块的根都满足这一条件，但显然并不是所有根都是割点，我们需要额外判断：记录 \(son\) 表示根的 不经过根无法连通 的儿子的个数，那么当 \(son>1\)，根即为割点。

为什么当 \(u\) 通过返祖边连接到 \(v\) 时，\(\text{low}_u\) 被 \(\text{dfn}_v\) 更新呢？首先强调一下 else 中还藏着一个 \(v\neq \rm fa\) 的判断。问题在于，用 \(\text{low}_v\) 更新并不能保证在返回时用树边更新 \(\text{low}_x\) 时（假设 \(x\) 是 \(v\) 的某个祖先）的用于更新的值不经过 \(x\) 的父亲。

很容易列举的反例是 \((x,y),(y,z),[z,x]\)（\([]\) 表示返祖边），如果 \(x\) 在进入 \(y\) 的子树之前进入另一个子树，更新了自己的 \(\rm low\) 且比自己的 \(\rm dfn\) 小，那么 \(\text{low}_y\leftarrow \text{low}_z\leftarrow \text{low}_x\)，我们就会以为 \(y\) 可以不通过 \(x\) 往上。

点双连通分量

懂了割点之后，这个还是很好理解的。需要注意根是孤儿的情况，而且一个割点可能被多个点双连通分量包含。

此时根不一定是割点，但我们仍需要利用它将剩余的点塞进一个点双连通分量中。另外，while() 循环应到 \(v\) 停止而不是 \(u\)，不然会塞进去一些另外的点。

for(int i=1;i<=n;++i)
    if(!dfn[i]) tarjan(i,i);

void tarjan(int u,int fa) {
	dfn[u]=low[u]=++idx; stk[++tp]=u;
	if(u==fa and !head[u]) {
		dcc[++Dcc].push_back(u);
		return;
	}
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(v==fa) continue;
		if(!dfn[v]) {
			tarjan(v,u);
			if(low[v]>=dfn[u]) {
                dcc[++Dcc].push_back(u);
                while(stk[tp]^v)
                    dcc[Dcc].push_back(stk[tp--]);
                dcc[Dcc].push_back(stk[tp--]);
            }
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

桥

若 \(u\rightarrow v\) 是一条返祖边，仍然是用 \(\text{dfn}_v\) 来更新，原因同上。需要注意 重边 的问题，这可能会使桥变成非桥。

void tarjan(int u,int fa) {
	dfn[u]=low[u]=++idx;
	bool Vis = false;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(!dfn[v]) {
			tarjan(v,u);
			if(low[v]>dfn[u]) 
                then (u,v) is a bridge.
			low[u]=min(low[u],low[v]);
		}
		else if(v==fa and !Vis) Vis = true;
		else low[u]=min(low[u],dfn[v]);
	}
}

边双连通分量

此时不在判断 low[v]>dfn[u] 的时候求解，会漏算孤儿的情况。

/*
网上很多代码有 inStack 数组，不太明白用来干嘛...
*/
void tarjan(int u,int fa) {
	dfn[u]=low[u]=++idx; stk[++tp]=u;
	bool Vis = false; int dot;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(!dfn[v]) {
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else if(v==fa and !Vis) Vis = true;
		else low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]) {
		++scc;
		do {
			bl[dot=stk[tp--]]=scc;
		} while(dot^u);
	}
}