前言

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

但是，( m 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;
}

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

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

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

很容易列举的反例是 ((x,y),(y,z),[z,x])（([]) 表示返祖边），如果 (x) 在进入 (y) 的子树之前进入另一个子树，更新了自己的 ( m low) 且比自己的 ( m dfn) 小，那么 ( ext{low}_yleftarrow ext{low}_zleftarrow ext{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 ightarrow v) 是一条返祖边，仍然是用 ( ext{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);
	}
}

有向图

强连通分量

此时也在循环外求解 ( m scc)，不然会漏算一些情况。

另外，还需要使用 inS[] 数组。只有 ( ext{inS}_v) 为真时才能更新，考虑满足这个条件的点一定满足 "已遍历过" 且 "不在栈里"，它已经被划分到一个强连通分量内了。这时的 ( ext{dfn}_v) 更小并不是可以走到 (u) 的祖先，而是这个强连通分量比 (u) 所在的先遍历到，所以不能用它来更新。

再提一嘴，这里用 (v) 更新时用 ( ext{dfn}_v, ext{low}_v) 更新均可。为啥捏？还是考虑之前证明用的 (x,y,z)，无论用什么更新，( ext{dfn}_y) 也不可能等于 ( ext{low}_v)，这对我们来说就够了。

void tarjan(int u,int fa) {
	dfn[u]=low[u]=++idx; int v;
	stk[++tp]=u; inS[u]=1;
	for(int i=0;i<n;++i) {
		if(~adj[u]>>(v=i)&1)
			continue;
		if(!dfn[v]) {
			tarjan(v,u);
			low[u] = min(low[u],low[v]);
		}
		else if(inS[v])
			low[u] = min(low[u],dfn[v]);
                // Notice that low[v] is also acceptable.
	}
	if(low[u]==dfn[u]) {
		do {
			inS[v=stk[tp--]]=0;
			bl[v]=scc;
		} while(u^v);
		++scc;
	}
}