\textit{low}_u:能够回溯到的最早的已经在栈中的结点。设以 u 为根的子树为 \textit{Subtree}_u。\textit{low}_u 定义为以下结点的 \textit{dfn} 的最小值:\textit{Subtree}_u 中的结点;从 \textit{Subtree}_u 通过一条不在搜索树上的边能到达的结点。
一个结点的子树内结点的 dfn 都大于该结点的 dfn。
从根开始的一条路径上的 dfn 严格递增,low 严格非降。
按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索。在搜索过程中,对于结点 u 和与其相邻的结点 v(v 不是 u 的父节点)考虑 3 种情况:
v 未被访问:继续对 v 进行深度搜索。在回溯过程中,用 \textit{low}_v 更新 \textit{low}_u。因为存在从 u 到 v 的直接路径,所以 v 能够回溯到的已经在栈中的结点,u 也一定能够回溯到。
v 被访问过,已经在栈中:根据 low 值的定义,用 \textit{dfn}_v 更新 \textit{low}_u。
v 被访问过,已不在栈中:说明 v 已搜索完毕,其所在连通分量已被处理,所以不用对其做操作。
将上述算法写成伪代码:
1 2 3 4 5 6 7 8 910
TARJAN_SEARCH(int u)
vis[u]=true
low[u]=dfn[u]=++dfncnt
push u to the stack
for each (u,v) then do
if v hasn't been searched then
TARJAN_SEARCH(v) // 搜索
low[u]=min(low[u],low[v]) // 回溯
else if v has been in the stack then
low[u]=min(low[u],dfn[v])
对于一个连通分量图,我们很容易想到,在该连通图中有且仅有一个 u 使得 \textit{dfn}_u=\textit{low}_u。该结点一定是在深度遍历的过程中,该连通分量中第一个被访问过的结点,因为它的 dfn 和 low 值最小,不会被该连通分量中的其他结点所影响。
因此,在回溯的过程中,判定 \textit{dfn}_u=\textit{low}_u 是否成立,如果成立,则栈中 u 及其上方的结点构成一个 SCC。
// C++ Versionintdfn[N],low[N],dfncnt,s[N],in_stack[N],tp;intscc[N],sc;// 结点 i 所在 SCC 的编号intsz[N];// 强连通 i 的大小voidtarjan(intu){low[u]=dfn[u]=++dfncnt,s[++tp]=u,in_stack[u]=1;for(inti=h[u];i;i=e[i].nex){constint&v=e[i].t;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}elseif(in_stack[v]){low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){++sc;while(s[tp]!=u){scc[s[tp]]=sc;sz[sc]++;in_stack[s[tp]]=0;--tp;}scc[s[tp]]=sc;sz[sc]++;in_stack[s[tp]]=0;--tp;}}
// C++ Version// g 是原图,g2 是反图voiddfs1(intu){vis[u]=true;for(intv:g[u])if(!vis[v])dfs1(v);s.push_back(u);}voiddfs2(intu){color[u]=sccCnt;for(intv:g2[u])if(!color[v])dfs2(v);}voidkosaraju(){sccCnt=0;for(inti=1;i<=n;++i)if(!vis[i])dfs1(i);for(inti=n;i>=1;--i)if(!color[s[i]]){++sccCnt;dfs2(s[i]);}}
// C++ Versionintgarbow(intu){stack1[++p1]=u;stack2[++p2]=u;low[u]=++dfs_clock;for(inti=head[u];i;i=e[i].next){intv=e[i].to;if(!low[v])garbow(v);elseif(!sccno[v])while(low[stack2[p2]]>low[v])p2--;}if(stack2[p2]==u){p2--;scc_cnt++;do{sccno[stack1[p1]]=scc_cnt;// all_scc[scc_cnt] ++;}while(stack1[p1--]!=u);}return0;}voidfind_scc(intn){dfs_clock=scc_cnt=0;p1=p2=0;memset(sccno,0,sizeof(sccno));memset(low,0,sizeof(low));for(inti=1;i<=n;i++)if(!low[i])garbow(i);}