有向图的强连通图——Kosaraju

有向图的强连通分量： 相互可达关系，每一个集合都是有向图的一个强连通分量SCC。   

把一个集合看成一个点，SCC就形成了一个有向无环图——DAG;

     

如果DFS选择不好，从A点开始DFS，就会把整张图遍历一遍。不是同一个SCC就混乱了，我们希望，可以利用SCC的拓扑序列，从后往前DFS，这样，每次都出来一个SCC，就不用分离了——Kosaraju算法。

——拓扑序列

反图——按照拓扑序列从后往前，就可以分离出每个SCC.

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 1000;

vector<int> G[Maxn],G2[Maxn];
vector<int> S;
int vis[Maxn],sccno[Maxn],scc_cnt;

void dfs1(int u)
{
    if(vis[u]) return ;
    vis[u] = 1;
    for(int i=0; i<G[u].size(); i++)
    {
        dfs1(G[u][i]);
    }
    S.push_back(u);
}

void dfs2 (int u)
{
    if(sccno[u]) return ;
    sccno[u] = scc_cnt;
    for(int i=0; i<G2[u].size(); i++)
    {
        dfs2(G2[u][i]);
    }
}

void find_scc(int n)
{
    scc_cnt = 0;
    S.clear();
    memset(sccno,0,sizeof(sccno));
    memset(vis,0,sizeof(vis));

    for(int i = 0; i<n; i++)
        dfs1(i);
    for(int i=n-1; i>=0; i--)
    {
        if(!sccno[S[i]])
        {
            scc_cnt++;
            dfs2(S[i]);
        }
    }
}