连通性问题 2

(4) 强连通分量（Gabow算法）  [邻接表]

Gabow算法与Tarjan算法的核心思想实质上是相通的，就是利用强连通分量必定是DFS的一棵子树这个重要性质，通过找出这个子树的根来求解强分量。

具体实现是利用一个栈 S 来保存DFS遇到的所有树边的另一端顶点，在找出强分量子树的根之后，弹出 S 中的顶点一一进行编号。

与Tarjan算法不同的是，Tarjan算法通过一个low数组来维护各个顶点能到达的最小前序编号，而 Gabow算法通过维护另一个栈来取代low数组，将前序编号值更大的顶点都弹出，然后通过栈顶的那个顶点来判断是否找到强分量子树的根。

int pre[N]; int color[N]; int S[N], P[N];

// 两个栈，S用来保存所有结点，P用来维护路径

int top_s, top_p; int cnt, id;

void DFS(int x)

{ int v;

pre[x] = cnt++; // 对前序编号编号

S[++top_s]=x;  // 将路径上遇到的树边顶点入栈  P[++top_p]=x;  for (edge *e=adj[x]; e!=NULL; e=e->next) {   v=e->v;   if (pre[v] == -1)      // 如果以前未遇到当前顶点，则对其进行DFS    DFS(v);   else if (color[v] == - 1)   // 如果当前顶点不属于强分量，    while (pre[P[top_p]] > pre[v]) // 就将路径栈P中大于当前顶点pre值的顶点都弹出     top_p--; }  if (P[top_p] == x)      // 如果P栈顶元素等于x，则找到强分量的根——x {   top_p--;   id++;   do   {    v = S[top_s--];     // 把S中的顶点弹出编号    color[v] = id;   } while (v != x); } } int Gabow() {  top_s=top_p=-1;  memset(pre,-1,sizeof(pre));  memset(color,-1,sizeof(color));  cnt=id=0;  for (int v=0; v<n; v++)   if (pre[v] == -1)    DFS(v);  return id;         // 返回id的值，这恰好是强连通分量的个数 }

(5) 有向图的传递闭包（Floyd-Warshall算法）  [邻接矩阵]

时间复杂度：O(n3)

Floyd-Warshall算法会把图上任意两个点的连通性都算出来。

bool f[N][N];    // 如果存在一条从i出发，到j结束的路径，f[j]=true。

……

// 预处理——可以在读图时完成

for (int i=0; i<n; i++)

for (int j=0; j<n; j++)   f[j] = (G[j]!=INF);

for (int k=0; k<n; k++) for (int i=0; i<n; i++) for (int j=0; j<n; j++)

  f[j] = f[j] || (f[k] && f[k][j]);