poj-1236-一行学习强连通分量2

poj-1236--一起学习强连通分量2

上一篇介绍过题目大意和kosaraju算法

本篇介绍tarjan算法。

引用一下讲解：

。

判断结点v'是否在栈中应在常数时间内完成，例如可以对每个结点保存一个是否在栈中的标记。

同一个强连通分量内的结点是无序的，但此算法具有如下性质：每个强连通分量都是在它的所有后继强连通分量被求出之后求得的。因此，如果将同一强连通分量收缩为一个结点而构成一个有向无环图，这些强连通分量被求出的顺序是这一新图的拓扑序的逆序#include <stdio.h>#include <stdlib.h>#include <string.h>#define nMax 110#define Min(x,y) (x<y?x:y)int map[nMax][nMax];int belong[nMax];int DFN[nMax],Low[nMax],stack[nMax];bool inStack[nMax];int n,index,cnt,top;int indegree[nMax],outdegree[nMax];void tarjan(int u)//tarjan算法{DFN[u] = Low[u] = ++index;//时间戳及low的初始化stack[top ++] = u;//堆栈inStack[u] = true;//是否已经在栈中for (int i = 1; i <= n; ++ i){if (map[u][i])//如果有边{if (!DFN[i])//如果还没访问过{tarjan(i);Low[u] = Min(Low[u], Low[i]);}else if (inStack[i])//如果已经在堆栈中{Low[u] = Min(Low[u], DFN[i]);}}}if (DFN[u] == Low[u])//强连通分量{cnt ++;while (1){int tmp = stack[-- top];belong[tmp] = cnt;//记录属于cnt强连通分量的所有点tmpinStack[tmp] = false;//并出栈if (tmp == u)//到达根节点{break;}}}}void output(){int inNum = 0,outNum = 0;memset(indegree, 0, sizeof(indegree));memset(outdegree, 0, sizeof(outdegree));for (int i = 1; i <= n; ++ i)//求强连通分量的出度和入度{for (int j = 1; j <= n; ++ j){if (map[i][j] && belong[i] != belong[j]){indegree[belong[j]] ++;outdegree[belong[i]] ++;}}}for (int i = 1; i <= cnt; ++ i)//求出出度和入度为0的点的个数{if (!indegree[i]){inNum ++;}if (!outdegree[i]){outNum ++;}}if (cnt == 1)//如果这个图强连通{printf("1\n0\n");}else//否则printf("%d\n%d\n",inNum, inNum > outNum ? inNum : outNum);}int main(){while (scanf("%d", &n) != EOF){memset(map, 0, sizeof(map));memset(inStack, false, sizeof(inStack));memset(DFN, 0, sizeof(DFN));index = cnt = top = 0;for (int i = 1; i <= n; ++ i){int v;while (scanf("%d", &v) && v){map[i][v] = 1;}}for (int i = 1; i <= n; ++ i){if (!DFN[i]){tarjan(i);//tarjan算法}}output();}return 0;}

 

 

 

虽然看了好多文章，理解了好多遍，但是在下还有一点不明白，忘大神指点一二：

就是求Low[u]的时候，为何不全是Min(Low[u], Low[i])为何还有在不在栈中之分？？？？？？？？？？？求解释。

最主要的是将Min(Low[u], DFN[i])改为Min(Low[u], Low[i])程序也能过，我相信这个地方肯定是有用的，也许我还没学习到吧。。。