Implementación de C ++ Depth First Search (DFS)

Estoy tratando de implementar el siguiente código DFS descrito en el libro Competitive Programming 1:

#include  #include  using namespace std; #define MAX 10 #define DFS_BLACK 1 #define DFS_WHITE -1 typedef pair ii; typedef vector vii; typedef vector vi; vi dfs_num; vector adj(MAX); void dfs(int u) { dfs_num[u] = DFS_BLACK; for (int i = 0; i < (int)adj[i].size(); i++) { ii v = adj[u][i]; if (dfs_num[v.first] == DFS_WHITE) dfs(v.first); } printf(" %d", u); } int main() { int v, e, x, y; scanf("%d %d", &v, &e); for (int i = 0; i < e; i++) { scanf("%d %d", &x, &y); adj[x].push_back(ii(y, 1)); adj[y].push_back(ii(x, 1)); } int numCC = 0; dfs_num.assign(v, DFS_WHITE); for (int i = 0; i < v; i++) if (dfs_num[i] == DFS_WHITE) printf("Component %d:", ++numCC), dfs(i), printf("\n"); printf("There are %d connected components\n", numCC); } 

Lo que estoy tratando de conseguir es:

 Input: Output: 9 7 Component 1: 0 1 2 3 4 0 1 Component 2: 5 1 2 Component 3: 6 7 8 1 3 There are 3 connected components 2 3 3 4 6 7 6 8 

Para el siguiente gráfico:

grafo1

Pero estoy obteniendo “Componente 1: 3 2 1” y luego se bloquea. ¿Qué estoy haciendo mal?

Cualquier ayuda es apreciada.

 for (int i = 0; i < (int)adj[i].size(); i++) { 

dentro:

 for (int i = 0; i < (int)adj[u].size(); i++) { // ^ u, not i 

Enlace demo en vivo

La lógica general parece estar bien, pero veo algunas cosas extrañas en los detalles:

  1. en la línea 17, el bucle for, ¿debería ser adj [u], en lugar de adj [i]?

Otras cosas que noté:

  1. No usar nombres de variables de una sola letra nos ayudaría mucho a entender su código … significa que obtendrá más respuestas.
  2. Sus componentes conectados se imprimirán en orden inverso (3 2 1, en lugar de 1 2 3) porque en dfs () tiene la impresión después de la llamada recursiva
  3. Me pregunto por qué está usando un par en las líneas 31 y 32 cuando el segundo int es 1, y nunca lo usa.