デプスファーストサーチアルゴリズム - 接続されたコンポーネントをカウントする

Question

こんにちは、私は質問があり、助けが必要なのかもしれません。おそらく、それはofftopicですが、私はすでにCode Reviewに投稿しました。私は擬似コードを使用してこれを書いていますが、私は立ち往生しています.1つの接続コンポーネントのVerticesの数が偶数であるかどうかを調べる必要があります。私の考えは、DFSを実装し、1つのカウンタを入れてから％2 == 0のカウンタが正しいかどうかをチェックすることです。私の問題はどこにカウンターを置くべきかわからないことです。 DFS：が主な方法だとしましょう。

G =（V、E）V-頂点、E-エッジ S-開始点（頂点）

DFS(G,s): 
boolean result <-- false 
Discovered[v] <-- false for all Vertices V(v) 
DFS1(G,s) 
if (DFS1(G,u) % 2==0) 
result <-- true 


DFS1(G,u): 
Discovered[u] <-- true 
// counter ++   But where I should initialize it?? 
foreach Edge (v,u) incident to u 
if !Discovered[v] 
DFS1(G,v)` 

Answer 1

あなたはそうのように、DFS1内のカウンタを宣言することができ、すべてのDFS1合計値で

int counter = 0 

DFS(G,s): 
    boolean result = false 
    Discovered[v] = false for all Vertices V(v) 
    DFS1(G,s) 
    if (counter % 2 == 0) 
     result = true 

DFS1(G,u): 
    Discovered[u] = true 
    counter++ 
    foreach Edge (v,u) incident to u 
     if !Discovered[v] 
      DFS1(G,v) 

Answer 2

もしTrueにDiscovered[u]を設定するときはいつでも、それは既に次にTrue、ありません新たに接続された頂点を見つけたので、あなたのカウンターを増やす必要があります。

DFS1は何も返さないので、特に、そのスコープ内にない変数で呼び出した後にチェックするので、返される内容を確認するのに役立つかどうかはわかりません。

DFS1(G,u): 
    Discovered[u] = true 
    int counter = 1      // Count actual node   
    foreach Edge (v,u) incident to u 
     if !Discovered[v] 
      counter += DFS1(G,v)  // Count descendant nodes 
    return counter 

をまたはグローバルスコープでカウンターを宣言し、ちょうど各DFS1コールでそれをインクリメント：