上次发的时候不小心被我设置成了只有自己可见,今天补上
dfn[now]表示在now点在dfs搜索树中的dfs序。
low[now]表示的是now通过后向边、横叉边能到达的dfn最小的点的dfs序。
我们取一个强连通分量中dfn最小的点作为整个强连通分量的代表元素。
因此low[now]的实际意义就是now所在的强连通分量的代表元素的点的dfn值。
tot表示当前图中强连通分量的数量。
col[now]表示now所在的强连通分量的编号,这个数组存在的意义是为了便于缩点时合并信息。
stack是手动维护的栈,这里栈的使用非常简单,没有必要使用STL,此外手动维护的栈常数显然更小。
没了。
代码如下,其他细节见注释
void tarjan(int now) { dfn[now]=low[now]=++Time; //初始化 stack[++top]=now; //入栈操作 v[now]=1; //v[]代表该点是否已入栈 for(int i=head[now];~i;i=e[i].nxt) //邻接表存图 if(!dfn[e[i].v]) //判断该点是否被搜索过 { tarjan(e[i].v); low[now]=min(low[now],low[e[i].v]); //回溯时更新low[ ],取最小值 } else if(v[e[i].v]) low[now]=min(low[now],dfn[e[i].v]); //一旦遇到已入栈的点,就将该点作为连通量的根 //这里用dfn[e[i].v]更新的原因是:这个点可能 //已经在另一个强连通分量中了但暂时尚未出栈,所 //以now不一定能到达low[e[i].v]但一定能到达dfn[e[i].v]. if(dfn[now]==low[now]) { int cur; tot++; do { cur=stack[top--]; v[cur]=false; //不要忘记出栈 col[cur]=tot; }while(now!=cur); } }