【算法】Tarjan算法求强连通分量

概念：

在有向图G中，如果两个定点u可以到达v，并且v也可以到达u，那么我们称这两个定点强连通。
如果有向图G的任意两个顶点都是强连通的，那么我们称G是一个强连通图。
一个有向图中的最大强连通子图，称为强连通分量。

tarjan的主要思想：

从一个点开始DFS，记录两个数组，dfn[]和low[]。

其中，dfn[i]指的是到达第i个点的时间。

low[i]指第i个点直接或间接可到达的点中的最小dfn[j]。

low[i]数组的初始值为dfn[i]。

举个例子，如图所示：

假如我们从第一个点开始跑DFS，dfn[1]=1,low[1]=1;那么走到第2个点时，标记dfn[2]=2;第三个点dfn[3]=2;dfn[4]=3;dfn[5]=3;dfn[6]=4;

同时，我们也可以得到另一个数组low[]:

low[1]=1;low[2]=1;low[3]=1;low[4]=1;low[5]=3;low[6]=4;

推广：

对于每一个没有被遍历到的点u，如果从当前点有一条到未遍历点u的有向边，则遍历到u，同时将点u入栈，时间戳+1并用dfn[u]记录到达点u的时间，枚举从u发出的每一条边，如果该边指向的点没有被访问过，那么继续dfs，回溯后low[u]=min(low[u],low[v])(其中v为u可以到达的点。)如果该点已经访问过并且该点仍在栈里，那么low[u]=min(low[u],dfn[v])。

证明：

略，作为一名OIer，知道结论就行了！！！

代码：

void tarjan(int u)

{

  low[u]=dfn[u]=++tim;

  instack[u]=1;stk[top++]=u;

  for(int i=H[u];i;i=X[i])

  {

    int v=P[i];

    if(!dfn[v])

    {

      tarjan(v);

      low[u]=min(low[u],low[v]);

    }

    else if(instack[v])

      low[u]=min(low[u],dfn[v]);

  }

  if(low[u]==dfn[u])

  {

    cnt++;

    int k;

    do

    {

      siz[cnt]++;

      k=stk[--top];

      belong[k]=cnt;

      instack[k]=0;

    }

    while(k!=u);

  }

}

例题：

迷宫城堡

Summer Holiday

Instantaneous Transference

宝藏

巴特西

【算法】Tarjan算法求强连通分量

最新文章

热门文章