概念

强联通：如果有向图中两个点vi和vj，其中vi到vj之间有一条有向路径，vj到vi有一条有向路径，则称vi，vj强联通。
强连通图：如果有向图G<V,E>中每两个点都强联通，则称该图是强连通图。
强连通分量：有向图的极大强联通子图称为强连通分量。

Tarjan算法的思想

  首先，介绍tarjan关键的两个数组dfn和low。dfn[i]记录该点被dfs的时间，low[i]记录该点所在的深度优先搜索树中的根节点的编号。在执行过程中需要栈来保存深度优先所遍历的节点并确定这些节点所处的强连通分量。
  其中low的更新规则是：如果当前点u的某一邻边的另一个端点v未被访问过，则low[u]=min（low[u],low[v]）;如果v点被访问过并且v一定在栈中，则low[u]=min(low[u],dfn[v])。

Tarjan算法的实现（HDU-1269）

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
const int maxn=10010;
const int maxm=100010;
vector<int> g[maxn];
int visit[maxn];
int dfn[maxn];
int low[maxn];
bool inStack[maxn];
int n,m,time;
int res;
int ans[maxn];
stack<int> st;
void init(int n0)
{
    memset(visit,0,sizeof(visit));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(ans,0,sizeof(ans));
    for(int i=0;i<=n0;i++)
    {
        g[i].clear();
    }
    while(!st.empty())
    {
        st.pop();
    }
    time=0;
    res=0;
}

void verjan(int i0)
{
    low[i0]=dfn[i0]=time++;
    st.push(i0);
    inStack[i0]=true;
    visit[i0]=1;
    for(int i=0;i<g[i0].size();i++)
    {
        int v=g[i0][i];
        if(visit[v]==0)
        {
            verjan(v);
            low[i0]=min(low[i0],low[v]);

        }else if(inStack[v])
        {
            low[i0]=min(low[i0],dfn[v]);
        }
    }
    if(dfn[i0]==low[i0])
    {
        int v0;
        do
        {
            v0=st.top();
            st.pop();
            inStack[v0]=0;
            ans[res]++;
        }while(v0!=i0);
         res++;
    }

}

int main()
{
    scanf("%d%d",&n,&m);
    while(n!=0||m!=0)
    {
        init(n);
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
        }
        verjan(1);
        if(ans[0]==n)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
        scanf("%d%d",&n,&m);

    }
    return 0;
}