DFSを使用してグラフ（adja）で接続されたコンポーネントを見つける

Question

今日、インターネットでDFSをどのように隣接リストで実行するかを調べてみましたが、これを正しく行う方法がわかりません。私がオンラインで見つけた最良の例は、Find connected components in a graph でしたが、彼の最初の方法を使ってもうまくいかないと思っていて、他の方法を試すには十分な自信がありません。これは私がこれまで持っているものである：（無視test_vectorとcc、私はcc_countは仕事に得ることに焦点を当てています）

エッジが含まれている構造体です：int型メインで

struct edge{ 
    int to; //copy of to_original (dont worry about this it's for a different functionality) 
    int w; //weight of edge 
    int from_original; //from vertex 
    int to_original; //to vertex 
} 

どこか：

cout << "conn: " << connected(adjA, test_vector) << endl; 

---

int connected(vector<list<edge>> &adjA, vector<short int> &cc){ 
     int v_size = adjA.size(); 
     vector<bool> discovered(false,v_size); 
     int cc_count = 0; 
     for(unsigned int u = 0; u < adjA.size(); u++){ 
      if(!discovered[u]){ 
       cout << u << endl; 
       discovered[u] = true; 
       cc_count+=1; 
       dfs(adjA,discovered,cc,cc_count,u); 
      } 
     } 
     return cc_count; 
    } 

---

void dfs(vector<list<edge>>&adjA, vector<bool> &discovered, vector<short int> &cc, int &cc_count,int u){ 
    for(unsigned int v = 0; v < adjA[u].size();v++){ 
     if(!discovered[v]){ 
      cout << v << endl; 
      discovered[v] = true; 
      dfs(adjA, discovered,cc,cc_count,v); 
     } 
    } 

    } 

cout << v << endl;およびcout << u << endlこれは、すべてのノードを1回訪問できたことを示しています。しかし、私は間違ってcc_countを増やしています。この隣接リストに：

0->[1]->[3]->[5] 
1->[0]->[2]->[3]->[4] 
2->[1]->[4] 
3->[0]->[1]->[4]->[5] 
4->[1]->[2]->[3]->[5]->[6] 
5->[0]->[3]->[4]->[6] 
6->[4]->[5] 

プログラムが出力：

0 
1 
2 
3 
4 
5 
6 
conn: 7 

グラフ全体が単一の構成要素であるのでconnは、1であるべきです。私はこれについて間違った方法をとっているように感じる。私は何をすべきか？ DFSまたはBFSを使用してこれを行うより良い方法はありますか？

貧弱な書式設定についてお詫び申し上げます。私は、スタックオーバーフローエラーを取り除くことを試みるだけで、ほぼ1時間を費やしました。

隣接リストによって表されるグラフが

Answer 1

あなたdfs方法は、すべてのエッジを見ていません。私はedgeが何であるかという質問から分かりませんが、ペアのようなもの（両方のエンドポイント）であると仮定できます。

その後

for(unsigned int v = 0; v < adjA[u].size();v++) { 
    // do something with v 
} 

は、実際に私は 'エッジ' であるかの説明を更新

for (auto const & e: adjA[u]) { 
    // do something with the endpoint of e other than u 
}