単純なDFSが無限ループに詰まっています

Question

私は、ノード数がnで、エッジ数がkであるC++で単純なDFSを実装しようとしています。それは無限ループで立ち往生されたいくつかの理由

：私はこのコードで間違っているつもりどこ

#include <bits/stdc++.h> 
using namespace std; 

#define pb push_back 
#define MAXV 1000 

void addEdge(vector<int> adj[], int u, int v){ 
    adj[u].pb(v); 
    adj[v].pb(u); 
} 

void DFSUtil(int u, vector<int> adj[], vector<int>& visited){ 
    visited[u] = 1; 
    cout << u << " "; 
    for(int i = 0;i<adj[u].size();i++){ 
     if(visited[adj[u][i]] == 0){ 
      DFSUtil(u,adj,visited); 
     } 
    } 
} 

void DFS(vector<int> adj[], int N){ 
    vector<int> visited(N, 0); 
    for(int u = 1;u<N;u++){ 
     if(visited[u] == 0){ 
      DFSUtil(u,adj,visited); 
      cout << "\n"; 
     } 
    } 
} 

int main(){ 
    int n,k,m,i,u,v; 
    scanf("%d %d",&n,&k); 

    vector<int> adj[n+1]; 

    for(i = 0;i<k;i++){ 
     scanf("%d %d",&u,&v); 
     addEdge(adj,u,v); 
    } 

    // find connected components 
    DFS(adj,n+1); 


    return 0; 
} 

は、誰かが私を指すもらえますか？

サンプル入力にテストする：

4 3 
1 2 
2 3 
1 4 

Answer 1

すべての手順をナビゲートした後、最終的に、私はバグを見つけることができています。

渡された値は、実際に同じ頂点を何度も繰り返し呼び出すため、無限ループと呼ばれるDFSUtil(u,adj,visited);ではなく、DFSUtil(adj[u][i],adj,visited);である必要があります。

Answer 2

void DFSUtil(int u, vector<int> adj[], vector<int>& visited){ 
    visited[u] = 1; 
    cout << u << " "; 
    for(int i = 0;i<adj[u].size();i++){ 
     int to = adj[u][i]; 
     if(visited[to] == 0){ 
      DFSUtil(to, adj, visited); 
     } 
    } 
}