有向图强连通分量之tarjan算法

这个算法我也不太懂，，看着伪代码，就把这个算法的模板给写出来了。。。

以后有机会再深入研究吧，这个学习态度，自己一下

代码：

#include<iostream>#include<vector>#include<cstring>using namespace std;const int maxn=1001;bool inStack[maxn];  //判断是否在栈中 int dfn[maxn];      //dfn表示深度遍历时的访问次序 int low[maxn];      //low表示可以回到的最小次序处int stap[maxn];    //存储遍历过的点，便于在找到强连通分量时输出int numVertex,numRoad,numAdj,index,stop;  //顶点数、路数、连通分量数、访问次序、控制输出的量 vector<int> myV[maxn];   //存储有向图 void storeMap(){    for(int j=0;j<maxn;j++)    {        myV[j].clear();    }        int from,to;    for(int i=0;i<numRoad;i++)    {        scanf("%d%d",&from,&to);        myV[from].push_back(to);    }}void tarjan(int i)  //tarjan算法 {    int j;        dfn[i]=low[i]=++index;  //深度遍历的访问次序     inStack[i]=true;        //访问到就相当于进栈     stap[++stop]=i;         //利用stap[]记录栈中的点，当找到连通分量时输出和删除         for(int k=0;k<myV[i].size();k++)   //一点一点的向下深度遍历     {        j=myV[i][k];   //取出当前和i相邻的点j                 if(!dfn[j])    //j没被访问过才访问，否则会重复求解连通分量         {            tarjan(j);                        low[i]=(low[i]>low[j])?low[j]:low[i];        }        else if(inStack[j] && dfn[j]<low[i])        {            low[i]=dfn[j];        }     }        if(dfn[i]==low[i])    {        numAdj++;                printf("The %dth Connected Component:\n",numAdj);         do        {            j=stap[stop--];            printf("%d ",j);             inStack[j]=false;        }while(i!=j);        printf("\n");     }}      void solve(){    //初始化条件     memset(dfn,0,sizeof(dfn));    memset(inStack,false,sizeof(inStack));    numAdj=index=stop=0;        for(int i=1;i<=numVertex;i++)   //从所有点出发找连通分量     {        if(!dfn[i])   //点i之前没出现过，否则就会重复找         {            tarjan(i);        }    }}        int main(){    while(scanf("%d%d",&numVertex,&numRoad)==2)    {        storeMap();                solve();                printf("The Sum Of Connected Component  Is : %d\n",numAdj);     }        system("pause");    return 0;}        

测试实例：

1、图形

2、输入及结果