强连通分量算法之——Tarjan

还是POJ_2762,前段时间用Kosaraju算法解决掉了，不过解决强连通分量的线性时间复杂度的算法还有两个，Tarjan，Gabow，今天把Tarjan看了下，感觉基本思想还是不难的，实现起来也算容易，不过我还不能证明其正确性。



Tarjan算法的基本思路就是，利用DFS去求强连通分量，具体步骤如下：

1.任意选取一个顶点做为DFS的起始位置，进行DFS。

2.在每次DFS中，先把discoverTime[now_node]，和lowlink[now_node]赋值为当前搜索时间，并把当前结点压入栈内，然后查看当前结点的所有后继结点，如果其后继结点尚未访问，则继续DFS下去，并且lowlink[now_node] = min(lowlink[now_node]，lowlink[当前结点的后继]).否则就检查该后继结点是否还在栈中,如果是的话则有 lowlink[now_node] = min(lowlink[now_node],discoverTime[该后继结点]);

说明:lowlink[u]表示包括u结点及其所有后继结点中最早被发现的时间，discoverTime[u]表示u结点的被发现时间.

3.查看lowlink[now_node]是否等于discoverTime[now_node]，如果是，则说明该结点是一个强连通分量的根，则把栈中的元素弹出，直到弹出的元素是now_node为止。至此就求出了一个SCC。

4.如果图中尚有未被访问的结点，那么就以这些结点中的任意一个作为起始位置，再次进行DFS，回到步骤二，直到所有结点都被访问过。至此，图的所有SCC都被求出.

伪代码如下：

algorithm tarjan is
  input: graph G = (V, E)
  output: set of strongly connected components (sets of vertices)
  index := 0
  S := empty
  for each v in V do
    if (v.index is undefined) then
      strongconnect(v)
    end if
  repeat
  function strongconnect(v)
    // Set the depth index for v to the smallest unused index
    v.index := index
    v.lowlink := index
    index := index + 1
    S.push(v)
    // Consider successors of v
    for each (v, w) in E do
      if (w.index is undefined) then
        // Successor w has not yet been visited; recurse on it
        strongconnect(w)
        v.lowlink := min(v.lowlink, w.lowlink)
      else if (w is in S) then
        // Successor w is in stack S and hence in the current SCC
        v.lowlink := min(v.lowlink, w.index)
      end if
    repeat
    // If v is a root node, pop the stack and generate an SCC
    if (v.lowlink = v.index) then
      start a new strongly connected component
      repeat
        w := S.pop()
        add w to current strongly connected component
      until (w = v)
      output the current strongly connected component
    end if
  end function

POJ_2762_Tarjan实现代码如下:

#include<iostream>
#include<vector>
#include<stack>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1001;
vector<int> g[MAXN];//adjlist
stack<int> S;
int vis[MAXN],store[MAXN],scc[MAXN][MAXN],scccnt,DFN[MAXN],LOW[MAXN],belong[MAXN],deg[MAXN];
#define MIN(a,b) a>b?b:a
void addEdge(int u,int v)
{
     g[u].push_back(v);
}
void init()
{
     for(int i=0;i<MAXN;i++)g[i].clear();
     while(!S.empty())S.pop();
     memset(vis,0,sizeof(vis));
     memset(store,0,sizeof(store));
     memset(scc,0,sizeof(scc));
     scccnt = 0;
}
void tarjan(int u,int n,int &time)
{
     DFN[u] = LOW[u] = time++;
     S.push(u);
     vis[u] = 1;store[u] = 1;
     for(int i=0;i<g[u].size();i++)
     {
         if(!vis[g[u][i]])//not visited
         {
             tarjan(g[u][i],n,time);
             LOW[u] = MIN(LOW[u],LOW[g[u][i]]);
         }
         else if(store[g[u][i]])//in the stack
         {
             LOW[u] = MIN(LOW[u],DFN[g[u][i]]);
         }
     }
     if(LOW[u]==DFN[u])
     {
         int v;
         do
         {
             v = S.top();
             S.pop();
             store[v] = 0;//out from the stack
             belong[v] = scccnt;
         }while(v!=u);
         scccnt++;
     }
}
void make_SCCG(int n)
{
     for(int i=1;i<=n;i++)
     {
         for(int j=0;j<g[i].size();j++)
         {
              if(belong[i]!=belong[g[i][j]])
              {
                  scc[belong[i]][belong[g[i][j]]]=1;
              }
         }
     }
}
bool calldfs2(int n)
{
     memset(vis,0,sizeof(vis));
     make_SCCG(n);
     memset(vis,0,sizeof(vis));
     memset(deg,0,sizeof(deg));
     for(int i=0;i<scccnt;i++)
     {
         for(int j=0;j<scccnt;j++)
         {
             if(scc[j][i])deg[i]++;
         }
     }
     int u,cnt;
     for(int i=0;i<scccnt;i++)
     {
         cnt = 0;
         for(int j=0;j<scccnt;j++)
         {
             if(deg[j]==0&&!vis[j])
             {
                 u = j;
                 cnt++;
             }
         }
         if(cnt!=1)return false;
         vis[u] = 1;
         for(int j=0;j<scccnt;j++)
         {
             if(scc[u][j])deg[j]--;
         }
     }
     return true;
}
int main()
{
    int n,m,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            addEdge(a,b);
        }
        int time = 1;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])tarjan(i,n,time);
        }
        bool ok = calldfs2(n);
        if(ok) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

参考资料:
[url]http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#Overview [/url]