两次dfs求连通分量

采用了《算法导论》求连通分量的思路
1. 对原图求dfs，记录每个点完成回溯的时间f
2. 求反向图gt
3. 按照回溯完成时间从大到小对每个点在图gt上进行dfs，每次dfs到的所有点为同一个连通分量

C++ 代码

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
using namespace std;

const int N = 10010;
vector<int> g[N], gt[N];
int n, m, timestamp, out[N];
int f[N], ver[N];
int scc[N], sizes[N], cnt;
bool vis[N];

void dfs1(int u) {
    vis[u] = true;
    for(int i=0;i<g[u].size();++i) {
        int v = g[u][i];
        if(!vis[v]) {
            dfs1(v);
        }
    }
    f[u]=++timestamp;
    ver[timestamp]=u;
}

void dfs2(int u, int id) {
    vis[u] = true;
    scc[u]=id;
    sizes[id]++;
    for(int i=0;i<gt[u].size();++i) {
        int v = gt[u][i];
        if(!vis[v]) dfs2(v, id);
    }
}

int main() {
    cin>>n>>m;
    while(m--) {
        int u, v;
        cin>>u>>v;
        g[u].push_back(v);
        gt[v].push_back(u);
    }
    for(int i=1;i<=n;++i) {
        if(!vis[i]) dfs1(i);
    }
    memset(vis, 0, sizeof(vis));
    for(int i=timestamp;i>=1;--i) {
        int x = ver[i];
        if(!vis[x]) {
            dfs2(x, ++cnt);
        }
    }
    for(int i=1;i<=n;++i) {
        for(int j=0;j<g[i].size();++j) {
            int v = g[i][j];
            if(scc[i]!=scc[v]) {
                out[scc[i]]++;
            }
        }
    }
    int zero = 0, ans = 0;
    for(int i=1;i<=cnt;++i) {
        if(out[i]==0) {
            zero++;
            ans+=sizes[i];
        }
        if(zero>1) {
            ans = 0;
            break;
        }
    }
    cout<<ans<<endl;
}