如何查找整個圖是否是一個強連通的組件？

我找到這個代碼，如果該圖是一個強連通分量如何查找整個圖是否是一個強連通的組件？

vector<int> G[2005]; 
int depth = 0; 
void dfs(int u) 
{ 
visited[u] = 1; 
low[u] = ++depth; 
    for(int i=0;i<G[u].size();++i) 
    { 
    int v = G[u][i]; 
    if(!visited[v]) 
     dfs(v); 
     low[u] = min(low[u],low[v]); 
    } 
}

我跑DFS（1），然後對我檢查每個頂點如果對所有頂點低[U] == 1和每個頂點都被訪問過。這是正確的方法嗎？它應該是，但不知何故它不起作用。這是我想要實現的一個問題http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=2938&mosmsg=Submission+received+with+ID+12516894

來源

2013-10-17 Tamim Addari

你有什麼數據結構？基本上和圖遍歷應該工作，當你標記訪問節點。 – dornhege

您正在遞增每次遞歸的深度。所以每個G [u] [i]的深度可能會不同，當我認爲如果它們在相同的循環中應該是相同的。 –

是的，但是我添加了'low [u] = min（low [u]，low [v]）這一行，所以如果它是一個連接組件，所有的最低值應該是1。頂點1. –

我會用Tarjan's algorithm。

本質上它是在O(|E|)時間內計算強連通組件。然後你可以簡單地看一下SCC的數量。如果不是1，那麼整個圖不是一個SCC。此外，您可以提供早期退出版本，例如，一旦找到第二次SCC退出。

一些C++作爲起始地：（但仍僞像）

vector<SCC> ComputeSCC(Graph& g) { 
    int index = 0; 
    vector<SCC> sccs; 
    stack<Vertex> s; 

    //for each vertex grab the SCC 
    for(auto v : g.vertices()) 
    if(v.index == -1) 
     StronglyConnected(g, v, index, s, sccs); 

    return sccs; 
} 

void StronglyConnected(Graph& g, Vertex& v, int& i, stack<Vertex>& s, vector<SCC>& sccs) { 
    v.index = i; 
    v.lowlink = i; 
    i++; 
    s.push_back(v); 

    //for each successor 
    for(auto e : v.successors()) { 
    if(e.target().index == -1) { 
     StronglyConnected(g, e.target(), i, sccs); 
     v.lowlink = min(v.lowlink, e.target().lowlink); 
    } 
    else 
     v.lowlink = min(v.lowlink, e.target().index); 
    } 

    //If v is a root node, pop the stack and generate an SCC 
    if(v.lowlink == v.index) { 
    sccs.push_back(SCC()); 
    Vertex w; 
    do { 
     w = S.pop(); 
     sccs.back().push_back(w); 
    } while(w != v); 
    } 
}

來源

2013-10-17 16:10:11 pippin1289

我應該像tarjans算法一樣維護堆棧嗎？因爲我不需要解決方案，所以我不需要堆棧。 –

如果您只想確定它是否爲一個SCC，則您可能不需要。一旦我嘗試創建一個新的SCC（在第一個之後），退出遞歸併停止。 – pippin1289

我已經完成了你所說的，這裏是我的代碼http://ideone.com/NLXKtT，但是我看到它在我給出的輸入方面失敗了。你可以看看這個問題http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=2938&mosmsg=Submission+received+with+ID+12516894 –

如何查找整個圖是否是一個強連通的組件？

回答

相關問題