就我所知，有三种时间复杂度为O(n)的方法可以求强连通分量，分别是Kosaraju、Tarjan和Gabow。

1. Kosaraju
   算法的步骤为
   • 对图G进行DFS，并按照遍历完成的先后顺序进行标号。
   • 将图G中所有的边反向得到G'。
   • 对G'进行DFS，每轮DFS都选择编号最大的点最为当前的遍历树的根。
   • 最后，遍历得到的森林就是SCC的集合。
   该算法的优点在于，最后得到的节点是按照拓扑序组织好的，在求解2-SAT的过程中十分方便。
2. Tarjan
   第一个求解SCC的算法，应用非常广泛，几乎任何和图的遍历有关的问题都可以套用Tarjan算法的思想（比如，求割点、桥、块等等）。
   在遍历时，对每一个节点定义时间戳，同时定义Low函数，含义为节点及其子孙通过非父子边的返祖边所能到达的最小时间戳。最后若Low函数等于其时间戳，则当前递归栈内存在一个SCC。
   代码如下：
   

   void dfs(int index) {
     low[index] = dfn[index] = cnt++;
     used[index] = 1;
     del[index] = 0;
     st[top++] = index;
     for (int i = last[index]; i!=-1; i = e[i].nxt)
       if (!used[e[i].y]) {
         dfs(e[i].y);
         if (low[index]>low[e[i].y]) low[index] = low[e[i].y];
       }
       else if (!del[e[i].y]) if (low[index]>dfn[e[i].y])
         low[index] = dfn[e[i].y];
     if (low[index]==dfn[index]) {
       do {
         root[st[--top]] = index;
         del[st[top]] = 1;
       } while (st[top]!=index);
     }
   }
   

3. Gabow
   算法的原理说起来太麻烦，还是直接给出代码。其实这个算法并不是很常用。
   

   #include <cstdio>
   #include <cstring>
   #include <stack>
   
   using namespace std;
   
   const int MAXN = 1000;
   
   struct node {
     int tar;
     node *nxt;
     node(int _tar,node *_nxt)
       : tar(_tar),nxt(_nxt) {}
   };
   
   node *g[MAXN];
   int n,m,co,all,dfn[MAXN],id[MAXN];
   stack<int> vec,path;
   
   void dfs(int x) {
     dfn[x] = co++;
     vec.push(x);
     path.push(x);
     for (node *i = g[x]; i!=NULL; i = i->nxt)
       if (dfn[i->tar]==-1) dfs(i->tar);
       else if (id[i->tar]==-1)
         while (dfn[path.top()]>dfn[i->tar]) path.pop();
     if (path.top()==x) path.pop();
     else return;
     for (int i; ;) {
       id[i = vec.top()] = all;
       vec.pop();
       if (i==x) break;
     }
     all++;
   }
   
   int main() {
     freopen("gabow.in","r",stdin);
     freopen("gabow.out","w",stdout);
     scanf("%d%d",&n,&m);
     memset(g,0,sizeof(g));
     for (int i = 0,a,b; i<m; i++) {
       scanf("%d%d",&a,&b); a--; b--;
       g[a] = new node(b,g[a]);
     }
     co = all = 0;
     memset(dfn,-1,sizeof(dfn));
     memset(id,-1,sizeof(id));
     for (int i = 0; i<n; i++)
       if (dfn[i]==-1) dfs(i);
     for (int i = 0; i<n; i++)
       printf("%d\n",id[i]);
     return 0;
   }
   

• Relative Posts