求有向圖的強連通分量個數（kosaraju算法）

有向圖的連通分量的求解思路

kosaraju算法

逛了很多部落格，感覺都很難懂，終于找到一篇能看懂的，摘要記錄一下

原部落格https://www.cnblogs.com/nullzx/p/6437926.html

關于連通分量是什麼自行百度，這裡主要說明連通分量的求解方法

基本思路：第一次DFS得出頂點的順序，根據頂點順序進行第二次DFS，也就是逆後序周遊（手動模拟一下堆棧就知道第二次DFS的過程就能得出答案）。

為什麼要兩次DFS?

如果從連通分量A中任意一個定點DFS，得不到正确結果。應該按照被指向的強連通分量的定點排在前面的順序進行DFS。上圖按照B3，B4，B5，A0，A1，A2的順序DFS。實際中我們隻要保證被指向的強連通分量的至少一個頂點排在指向這個連通分量的所有頂點前面即可，比如B3，A0，A1，A2，B4，B5；B3排在強連通分量A所有定點的前面。

如何得到滿足要求的頂點順序：對原圖取反，從反向圖的任意節點開始進行DFS的逆後序周遊

DFS的逆後序周遊指：如果目前頂點沒被通路，先周遊完與目前頂點相連的且未被通路的所有其他頂點，然後将目前頂點加入棧，最後從棧頂到棧底的順序是我們需要的頂點順序。

其實它是利用了有向圖的方向性：例如在上圖中，強連通分量A和B不管正反圖都能自己跑一圈，但是從A到B就隻能從A2跑到B3，不可能從B3跑到A2，是以将圖取反（注意圖取反，不能從A2跑到B3，頂點順序被記錄，按頂點順序一個個彈出周遊，之前周遊過的點就不用再周遊），做成反向圖，再逆後序周遊，A0在棧頂，周遊一圈，不能從A2跑到B3，就得到一個連通分量（如下圖）

接下來原部落客的代碼看不懂，還是百度百科kosaraju算法裡面的代碼好

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
#define INF 999999999
#define MAXN 551
#define MOD 1000000009
int n;
int mp[MAXN][MAXN], nmp[MAXN][MAXN], vis[MAXN];
stack<int> s;
void dfs_1(int v)
{
//    cout << v <<endl;
    vis[v] = 1;
    for(int i = 1; i <= n; ++i)
        if(!vis[i] && mp[v][i])
        dfs_1(i);
    s.push(v);
}
void dfs_2(int v)
{
    vis[v] = 1;
    for(int i = 1; i <= n; ++i)
        if(!vis[i] && nmp[v][i])
        dfs_2(i);
}
int kosaraju()
{
    while(!s.empty())
        s.pop();
    memset(vis, 0, sizeof(vis));
    
    for(int i = 1; i <= n; ++i)
        if(!vis[i])
        dfs_1(i);
        
    int ans=0;
    memset(vis, 0, sizeof(vis));
    
    while(!s.empty())
    {
        int v = s.top();
        s.pop();
        if(!vis[v])
        {
//            cout << v <<endl;
            ans++;
            dfs_2(v);
        }
    }
    return ans;
}
int main()
{
    int m, a, b;
    //n個點，m條邊
    cin >> n >>m;
    memset(mp, 0, sizeof(mp));
    memset(nmp, 0, sizeof(nmp));
    for(int i = 0; i < m; ++i)
    {
        cin >> a >>b;
        mp[a][b] = 1;
        nmp[b][a] = 1;
    }
    cout << kosaraju() <<endl;
    return 0;
}
/*
5 5
1 2
2 1
2 3
3 4
4 1
樣例輸出：
2
*/