グラフ：DFSを使用してundirectdグラフのサイクルを検出する方法

Question

DFSの実装は次のとおりです。グラフにサイクルが存在するかどうかを検出できるように、実装したいと思います。私はそれを実装する方法を確認していない接続されている要素の数）

#include <iostream> 
#include <vector> 
using namespace std; 

vector <int> adj[10]; 
int visited[10]; 
bool flag=false; 

void dfs(int s) { 
    visited[s] = 0; 
    for(int i = 0;i < adj[s].size();++i) { 
    if(visited[adj[s][i]] == -1) 
     dfs(adj[s][i]); 
    else if (visited[adj[s][i]] ==1){ 
     flag=true; 
     // cout<<"g"; 
     return; 
    } 
    } 
    visited[s]=1; 
} 

void initialize() { 
    for(int i = 0;i < 10;++i) 
    visited[i] = -1; 
} 

int main() { 
    int nodes, edges, x, y ; 
    cin >> nodes;      //Number of nodes 
    cin >> edges;      //Number of edges 
    for(int i = 0;i < edges;++i) { 
    cin >> x >> y;  
    adj[x].push_back(y);     //Edge from vertex x to vertex y 
    adj[y].push_back(x);     //Edge from vertex y to vertex x 
    } 

    initialize();       //Initialize all nodes as not visited 

    for(int i = 1;i <= nodes;++i) { 
    if(visited[i] == false)  { 
     dfs(i); 
    } 

    } 
    if (flag) 
     cout<<"Graph contains cycles"<<endl; 
    else 
     cout<<"No cycles"<<endl; 
    return 0; 
} 

を見つけるために使用する、誰もがそれで私を助けることができます。

を編集しようとしました。 visited内の各要素は-1そのために設定されたため、あなたのコードがチェックを開始しませんでした

for(int i = 0;i < nodes;++i) { 
    if(visited[i] == -1)  { 
    dfs(i); 
    } 
} 

：私は間違って

Answer 1

私は、初期化コールの後にループを変更したつもりですどこか分からないのですかスキップしました。だからこの変更でそれは動作します。

グローバル変数adjとvistedのサイズを調べて、できるだけローカルにすることをお勧めします。 11以上のノードが入力されると、このコードは機能しなくなります。質問の

編集は「あなたは私が非連結グラフをチェックしない方法を教えてもらえます？」

変更同じループをこれに：

int nr_of_graphs = 0; 
for(int i = 0;i < nodes;++i) { 
    if(visited[i] == -1)  { 
    ++nr_of_graphs; 
    dfs(i); 
    } 
} 
cout << "Nr of disconnected subgraphs " << nr_of_graphs << endl; 

dfs(i)は、各まだ訪れていないノードのために呼ばれています。したがって、この関数がmainから呼び出された回数を数え、切断された部分グラフの数を返します。