有向圖的強連通分量： 相互可達關系，每一個集合都是有向圖的一個強連通分量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]);
        }
    }
}

總結

以上是生活随笔為你收集整理的有向图的强连通图——Kosaraju的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。