Comment passer une variable en décroissance continue en récursivité? [C++]

Question

J'essaie de résoudre le problème Un nœud trop loin comme spécifié dans https://uva.onlinejudge.org/external/3/336.pdf. J'essaye d'employer la profondeur-première-recherche (DFS) pour cela. Mais je ne peux pas obtenir la réponse. J'utilise la récursivité pour DFS et j'ai passé un paramètre ttl à la fonction DFS. Autant que je sache, ttl a besoin de diminuer pour chaque récursion successive mais il arrive qu'il soit décrémenté pour chaque récursion. Voici le code: -

 #include<iostream> 
     #include<list> 
     #include<stdio.h> 

     using namespace std; 

     class Graph 
     { 
      int V; 
      list<int> *adj; 
      public: 
       Graph(int V); 
       void addEdge(int v, int w); 
       void DFSUtil(int v, bool visited[], int ttl); 
       void DFS(int s, int ttl); 
     }; 

     Graph::Graph(int V) 
     { 
      this->V = V; 
      adj = new list<int>[V]; 
     } 

     void Graph::addEdge(int v, int w) 
     { 
      adj[v].push_back(w); 
      adj[w].push_back(v); 
     } 

     void Graph::DFSUtil(int v, bool visited[], int ttl) 
     { 
      visited[v] = true; 
      cout << endl; 
      int k = ttl; 
      if(k>=0) 
      { 
       cout << ttl << " " << v ; 
       list<int>::iterator i; 
       for(i = adj[v].begin(); i!=adj[v].end(); ++i) 
       { 
        if(!visited[*i]) 
        { 
         int b = ttl - 1; 
         DFSUtil(*i, visited, b); 
        } 
       } 
      } 
     } 

     void Graph::DFS(int s, int ttl) 
     { 
      bool *visited = new bool[V]; 
      for(int i = 0; i < V; i++) 
      { 
       visited[i] = false; 
      } 
      DFSUtil(s, visited,ttl); 
     } 

     int main() 
     { 
      Graph g(100); 
      int nc; 
      while(scanf("%d",&nc)) 
      { 
       if(nc == 0) 
       { 
        break; 
       } 
       for(int i = 0; i < nc; i++) 
       { 
        int v, w; 
        cin >> v >> w; 
        g.addEdge(v, w); 
       } 
       int s, ttl; 
       while(scanf("%d%d",&s,&ttl)) 
       { 
        if(s == 0 && ttl == 0) 
        { 
         break; 
        } 
        g.DFS(s, ttl); 
       } 
      } 
      return 0; 
     } 

L'entrée est aussi: -

 16 
     10 15 15 20 20 25 10 30 30 47 47 50 25 45 45 65 
     15 35 35 55 20 40 50 55 35 40 55 60 40 60 60 65 
     35 2 35 3 0 0 
     0 

et la sortie est: -

2 35 
1 15 
0 10 

0 20 


1 55 
0 50 

0 60 

Alors, comment puis-je passer ttl telle qu'elle obtient décrémenté pour les appels de récursion respectifs seulement?

Editer: - La question me semble également ambiguë. Il dit qu'il n'y aura pas plus d'une ligne de communication (directe) entre n'importe quelle paire de nœuds. Mais, selon la sortie, cela suggère que le graphique n'est pas dirigé. Editer: - J'ai édité le code et j'ai trouvé la sortie donnée. Le problème est que le noeud 35 a une arête à 40 et le noeud 60 aussi. Lorsque la récursion passe à 60, il visite 40 mais puisque ttl est> 0, il n'est pas imprimé. Mais puisque 35 a un avantage pour 40, il devrait être imprimé. C'est là que je suis coincé.

Answer 1

Il semble que le problème ne soit pas avec ttl. Bien qu'il devrait y avoir une déclaration se terminant comme

 if(ttl<0) 
      return; 

Mais la question principale est - Comme les tableaux sont passés par adresse, le tableau reste visité modifié par récursion successives. Ainsi, une fois qu'il essaie de parcourir la boucle for, le tableau visité en raison de la récursion précédente est modifié. Supposons, s'il y a 3 nœuds, et les arêtes sont 1 2, 1 3, 2 3. Ensuite, si nous donnons node et ttl à 1 3. alors cela devrait donner -
1-> 2-> 3,1 -> 3-> 2.
Mais dans ce cas de code, puisque dans le premier cas 1-> 2-> 3, il a déjà traversé 3, alors le rendu [3] devient vrai provoquant l'omission de 3 à l'itération suivante. Donc, cela donne seulement 1-> 2-> 3.
La solution est à la place de tableau, vous pouvez utiliser Vector l'obligeant à passer par valeur.