找到在無向圖的連接分量的數目

在使用者輸入的頂點的數量（Ñ），然後 - 在下一Ñ線 - 頂點是如何連接的，即該號碼X在i -th line表示頂點i與頂點x連接（該圖是無向的）。任務是在此圖中查找連接組件的數量，並且我的代碼 - 出於某種原因，我無法找到 - 輸出錯誤值（例如，輸入爲，我的代碼輸出爲而不是）。任何幫助不勝感激。找到在無向圖的連接分量的數目

#include <iostream> 
#include <vector> 
#include <stack> 

int n; 

using namespace std; 
vector <int> graph[1000006]; 
int components[1000006]; 
int no_of_components; 
stack <int> mystack; 

int main(){ 

    cin >> n; 

    for (int i=0; i<n; i++){ 
     int X; 
     cin >> X; 
     graph[X-1].push_back(i); 
    } 

    for (int i=0; i<n; i++){ 

     if (components[i]>0) continue; 

     no_of_components++; 

     mystack.push(i); 
     components[i]=no_of_components; 

     while (mystack.empty()==false){ 
      int v; 

      v=mystack.top(); 
      mystack.pop(); 

      for (int u=0; u<graph[v].size(); u++){ 
       if (components[u]>0) continue; 

       mystack.push(u); 
       components[u]=no_of_components; 

      } 
     } 
    } 

    cout << no_of_components; 

    return 0; 

}

來源

2016-02-19 VanDerWarden

在你的代碼中有反u它允許你通過節點V的連接迭代之間的混淆，以及連接本身：

v是一個節點
graph[v]是連接的向量
u是連接向量中的索引
因此graph[v][u]是連接到v和component[graph[v][u]]節點你有分量的標記更新

所以，你必須糾正內部的循環如下：

 for (int u=0; u<graph[v].size(); u++){ 
      if (components[graph[v][u]]>0) continue; 

      mystack.push(graph[v][u]); 
      components[graph[v][u]]=no_of_components; 

     }

然後按預期工作。

Online demo

來源

2016-02-19 18:44:30 Christophe

@hetajr爲了避免任何懷疑，我已經更新了在線演示，顯示圖形和顯示與算法的修正版本中確定的分組。 – Christophe

找到在無向圖的連接分量的數目

回答

相關問題