グラフのサイクル中のノード数

Question

グラフの1サイクルでノード数を調べようとしています。私はグラフのすべてのサイクルでノードの数を計算するために再帰とDFSを使用しています。ここではC++の計算関数です。

int iscyclic(int node,bool visited[],bool rec[],vector<int>g[]) 
{ 
    if(!visited[node]) 
{ 
    visited[node] = true; 
    rec[node] = true; 
    vector<int>::iterator it; 
    for(it=g[node].begin();it!=g[node].end();it++) 
    { 
     if(!visited[*it] && iscyclic(*it,visited,rec,g)) 
     { 
      kount++; 
     } 
     else if(rec[*it]) 
      kount++; 
    } 
} 
rec[node] = false; 
return kount; 
} 

Visitedとrec配列は、デフォルトではfalseに設定されているとkountは、グローバル0として設定されています。 kountは、有向グラフのサイクル内のノード数を計算することになっています。答えが間違っているケースがあります。助けてください。私は最近グラフ理論を学び始めました。

Answer 1

あなたはこれを行うべきではありません。

else if(rec[*it]) 
    kount++; 

はまた、あなたが開始ノード（あなたが持つ関数を呼び出す1）は本当にサイクルの一部であることを確認する必要があります。

第3の事柄 - このブランチでサイクルが発生したかどうかに基づいて、実際にtrueまたはfalseを返す必要がある場合は、関数の結果としてkcountを返します。