今天上午学习Tarjan求强连通分量。首先引进一个概念：搜索树。
    我们在做DFS搜索时会出现一棵树，如图：

搜索树中，会有许多边。其中，实线是树边，就是搜索树中子节点与父节点相连的边。稀虚线是后向边，又称返祖边，是一个点直

接连向他祖宗的边。红线是后向边，是一个点直接连接他子孙的边。密虚线是横向边，就是不是以上三种的边。
    Tarjan求强连通分量时会有两个数组：low和dfn。low数组是为i或i的子树能够追溯到的最早的栈中节点

的次序号，dfn数组是在DFS中该节点i被搜索的次序(时间戳)，也就是被访问的时间。在Tarjan深搜时，如果发现子节点的low值低

于父节点的low值，那么就直接将父节点的low值赋到子节点上，回溯时也是如此。当回溯到一个点他的dfn值与low值相等时，一个

强连通分量就求出来了。下面放个视频来体现以下过程。视频当中中括号里的值就是low值。

最后，上代码：

#include <bits/stdc++.h>
#include <windows.h>
#define MAXN 1005
using namespace std;
vector <int> edge[MAXN];
int dfn[MAXN],low[MAXN];
stack <int> st;
bool in_st[MAXN];
int cnt;
int ans;
bool aa[MAXN];
int m,n;
int scc[MAXN],sc;
int sz[MAXN];
void input()
{
    cin>>n>>m;
    int tmp1,tmp2;
    for (int i=1;i<=m;i++)
    {
        cin>>tmp1>>tmp2;
        edge[tmp1].push_back(tmp2);
    }
}
void tarjan(int x)
{
    st.push(x);
    in_st[x]=1;
    dfn[x]=++cnt;
    low[x]=cnt;
    for (int i=0;i<edge[x].size();i++)
    {
        int y=edge[x][i];
        if (!dfn[y]) 
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if (in_st[x]) low[x]=min(low[x],low[y]);
    }
    if (dfn[x]==low[x])
    {
        ++sc;
        while (st.top()!=x) {
          scc[st.top()]=sc;
          sz[sc]++;
          in_st[st.top()] = 0;
          st.pop();
        }
        scc[st.top()] = sc;
        sz[sc]++;
        in_st[st.top()] = 0;
        st.pop();
    }
}
int main()
{
    input();
    for (int i=1;i<=n;i++)
    if (!dfn[i]) tarjan(1);
    for (int i=1;i<=n;i++)
    if (!aa[scc[i]])
    {
        ans++;
        aa[scc[i]]=1;
    }
    cout<<ans<<endl;
    return 0;
}

    在代码实现过程中，还要注意：在每一层搜索完成后，需要再次更新low值，并取出强连通分量。