tarjan算法求强连通分量<模板>

上次发的时候不小心被我设置成了只有自己可见,今天补上
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);
    }
}
上一篇:如何导出存储过程、函数、包和触发器的定义语句?如何导出表和索引的创建语句?...


下一篇:「图论」连通性问题