Простой DFS застрял в бесконечном цикле переполнения стека

Question

Простой DFS застрял в бесконечном цикле переполнения стека

Я пытаюсь реализовать простой DFS в C ++ с n количество узлов и k количество ребер

По какой-то причине он застревает в бесконечном цикле:

#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;
}

Может ли кто-нибудь указать мне, где я ошибаюсь с этим кодом?

Пример ввода для тестирования:

-1

c++dfs

Решение

Другие решения

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);
}
}
}

1

Источник

Accepted Answer

После навигации по всем шагам, наконец, я смог найти ошибку.

Переданное значение должно было быть DFSUtil(adj[u][i],adj,visited); вместо DFSUtil(u,adj,visited); который снова и снова вызывает одну и ту же вершину и, следовательно, бесконечный цикл.

1