首先明确两个概念：时间戳和追溯点
    时间戳：dfn[u]表示节点u深度优先遍历的序号
    追溯点：low[n]表示节点u或u的子孙能通过非父子边追溯到的dfn最小的节点序号，即回到最早的过去。
    Targan算法是用来处理强连通问题(a->b且b->a)的。
    原理1:求桥

    1. #include<iostream>
    2. #include<cstring>
    3. using namespace std;
    4. const int maxn=1000+5;
    5. int n,m,head[maxn],cnt;
    6. int low[maxn],dfn[maxn],num;
    7. struct Edge{
    8.     int to,next;
    9. }e[maxn<<1];
    11. void add(int u,int v){
    12.     e[++cnt].next=head[u];
    13.     e[cnt].to=v;
    14.     head[u]=cnt;    
    15. }
    17. void tarjan(int u,int fa){//求桥 
    18.     dfn[u]=low[u]=++num;
    19.     for(int i=head[u];i;i=e[i].next){
    20.         int v=e[i].to;
    21.         if(v==fa)
    22.             continue;
    23.         if(!dfn[v]){
    24.             tarjan(v,u);
    25.             low[u]=min(low[u],low[v]);
    26.             if(low[v]>dfn[u])
    27.                 cout<<u<<"—"<<v<<"是桥"<<endl; 
    28.         }
    29.         else
    30.             low[u]=min(low[u],dfn[v]);
    31.     }
    32. }
    34. void init(){
    35.     memset(head,0,sizeof(head));
    36.     memset(low,0,sizeof(low));
    37.     memset(dfn,0,sizeof(dfn));
    38.     cnt=num=0;
    39. }
    41. int main(){
    42.     while(cin>>n>>m){
    43.         init();
    44.         int u,v;
    45.         while(m--){
    46.             cin>>u>>v;
    47.             add(u,v);
    48.             add(v,u);
    49.         }
    50.         for(int i=1;i<=n;i++)
    51.             if(!dfn[i])
    52.                 tarjan(1,0);
    53.     }
    54.     return 0;
    55. }

    原理二:求割点

    1. #include<iostream>
    2. #include<cstring>
    3. using namespace std;
    4. const int maxn=1000+5;
    5. int n,m,head[maxn],cnt,root;
    6. int low[maxn],dfn[maxn],num;
    7. struct Edge{
    8.     int to,next;
    9. }e[maxn<<1];
    11. void add(int u,int v){
    12.     e[++cnt].next=head[u];
    13.     e[cnt].to=v;
    14.     head[u]=cnt;    
    15. }
    17. void tarjan(int u,int fa){//求割点 
    18.     dfn[u]=low[u]=++num;
    19.     int count=0;
    20.     for(int i=head[u];i;i=e[i].next){
    21.         int v=e[i].to;
    22.         if(v==fa)
    23.             continue;
    24.         if(!dfn[v]){
    25.             tarjan(v,u);
    26.             low[u]=min(low[u],low[v]);
    27.             if(low[v]>=dfn[u]){
    28.                 count++;
    29.                 if(u!=root||count>1)
    30.                     cout<<u<<"是割点"<<endl; 
    31.             }    
    32.         }
    33.         else
    34.             low[u]=min(low[u],dfn[v]);
    35.     }
    36. }
    38. void init(){
    39.     memset(head,0,sizeof(head));
    40.     memset(low,0,sizeof(low));
    41.     memset(dfn,0,sizeof(dfn));
    42.     cnt=num=0;
    43. }
    45. int main(){
    46.     while(cin>>n>>m){
    47.         init();
    48.         int u,v;
    49.         while(m--){
    50.             cin>>u>>v;
    51.             add(u,v);
    52.             add(v,u);
    53.         }
    54.         for(int i=1;i<=n;i++)
    55.             if(!dfn[i]){
    56.                 root=i;
    57.                 tarjan(i,0);
    58.             } 
    59.     }
    60.     return 0;
    61. }

    原理三：求强连通分量

    #include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=1000+5;
int n,m,head[maxn],cnt;
int low[maxn],dfn[maxn],num;
stack<int>s;
bool ins[maxn];
struct Edge{
    int to,next;
}e[maxn<<1];

void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;    
}

void tarjan(int u){//求强连通分量 
    low[u]=dfn[u]=++num;
    cout<<"low["<<u<<"]="<<low[u]<<"\tdfn["<<u<<"]="<<dfn[u]<<endl;
    ins[u]=true;
    s.push(u);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
            cout<<"update1:low["<<u<<"]="<<low[u]<<endl;
        }
        else if(ins[v]){
            low[u]=min(low[u],dfn[v]);
            cout<<"update2:low["<<u<<"]="<<low[u]<<endl;
        }    
    }
    if(low[u]==dfn[u]){
        int v;
        cout<<"强连通分量：";
        do{
            v=s.top();
            s.pop();
            cout<<v<<" ";
            ins[v]=false;
        }while(v!=u);
        cout<<endl;
    }
}

void init(){
    memset(head,0,sizeof(head));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(ins,0,sizeof(ins));
    cnt=num=0;
}

int main(){
    while(cin>>n>>m){
        init();
        int u,v;
        while(m--){
            cin>>u>>v;
            add(u,v);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i);
    }
    return 0;
}
/*测试数据 
5 8
1 3
1 2
3 5
3 4
3 2
4 5
4 1
5 1
*/

    实际应用：

     #include<cstdio>

 #include<algorithm>

 #include<string.h>

 using namespace std;

 struct node

 {

     int v,next;

 } edge[1001];

 int DFN[1001],LOW[1001];

 int stack[1001],heads[1001],visit[1001],cnt,tot,index;

 void add(int x,int y)//链式前向心

 {

     edge[++cnt].next=heads[x];

     edge[cnt].v = y;

     heads[x]=cnt;

     return ;

 }

 void tarjan(int x)//代表第几个点在处理。递归的是点。

 {

     DFN[x]=LOW[x]=++tot;

     stack[++index]=x;

     visit[x]=1;//表示在栈里

     for(int i=heads[x]; ~i ;i=edge[i].next)

     {

         if(!DFN[edge[i].v])  //如果没访问过

         {

             tarjan(edge[i].v);//往下进行延伸，开始递归

             LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情。

         }

         else if(visit[edge[i].v ])   //如果访问过，并且还在栈里。

         {

             LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子／父亲。就是链接对应关系

         }

     }

     if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。

     {

         do

         {

             printf("%d ",stack[index]);

             visit[stack[index]]=0;

             index--;

         }

         while(x!=stack[index+1]); //出栈，直到找到最小根。

         printf("
");

     }

     return ;

 }

 int main()

 {

     memset(heads,-1,sizeof(heads));

     int n,m;

     scanf("%d%d",&n,&m);

     int x,y;

     for(int i=1; i<=m; i++)

     {

         scanf("%d%d",&x,&y);

         add(x,y);

     }

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

         if(!DFN[i])tarjan(i);//当这个点没有访问过，就从此点开始。防止图没走完

     return 0;

 }