Wie übergebe ich eine stetig abnehmende Variable in der Rekursion? [C++]

Question

Ich versuche, das Problem zu lösen Ein Knoten zu weit wie in https://uva.onlinejudge.org/external/3/336.pdf angegeben. Ich versuche die Tiefensuche (DFS) dafür zu verwenden. Aber ich kann die Antwort nicht bekommen. Ich verwende Rekursion für DFS und ich habe einen Parameter ttl an die Funktion DFS übergeben. So weit ich weiß ttl muss für jede nachfolgende Rekursion abnehmen, aber es passiert, dass es für jede Rekursion dekrementiert wird. Hier ist der 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; 
     } 

Der Eingang ist als: -

 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 

und der Ausgang ist: -

2 35 
1 15 
0 10 

0 20 


1 55 
0 50 

0 60 

So wie gehe ich ttl, so dass es bekommt für die jeweiligen Rekursionsaufrufe nur dekrementiert?

Edit: - Die Frage scheint mir auch mehrdeutig. Es besagt, dass es zwischen einem beliebigen Knotenpaar nicht mehr als eine (direkte) Kommunikationsleitung geben wird. Aber laut der Ausgabe schlägt es vor, dass der Graph ungerichtet ist.

Bearbeiten: - Ich bearbeitet den Code und kam mit der angegebenen Ausgabe. Das Problem ist, dass Knoten 35 eine Kante zu 40 hat und Knoten 60 ebenfalls. Wenn die Rekursion 60 erreicht, besucht sie 40, aber da ttl> 0 ist, wird sie nicht gedruckt. Aber da 35 eine Kante für 40 hat, sollte es gedruckt werden. Hier stecke ich fest.

Answer 1

Es scheint das Problem ist nicht mit TTL. Obwohl es sollte wie

 if(ttl<0) 
      return; 

eine Abschlusserklärung sein, aber das Hauptproblem ist - Da Arrays von Adresse übergeben werden, die besucht Array durch sukzessive Rekursion geändert bleibt. Sobald es versucht, die for-Schleife zu durchlaufen, wird das besuchte Array wegen der vorherigen Rekursion modifiziert. Angenommen, es gibt 3 Knoten, und die Kanten sind 1 2, 1 3, 2 3. Wenn wir dann node und ttl als 1 3 angeben, dann sollte es im Grunde geben als -
1-> 2-> 3,1 -> 3-> 2.
Aber in diesem Code-Fall, da im ersten Fall 1-> 2-> 3, hat es schon 3 durchlaufen, also besucht [3] wird wahr, wodurch es 3 in der nächsten Iteration zu überspringen. Also gibt es nur 1-> 2-> 3.
Die Lösung ist anstelle von Array, Sie können Vector verwenden, wodurch es nach Wert übergeben wird.