Как передать непрерывную уменьшающуюся переменную в рекурсии? [C++]

Question

Я пытаюсь решить проблему Узел слишком далеко, как указано в https://uva.onlinejudge.org/external/3/336.pdf. Я пытаюсь использовать для этого поиск по глубине (DFS). Но я не могу получить ответ. Я использую рекурсию для DFS, и я передал параметр ttl функции DFS. Насколько мне известно, ttl необходимо уменьшить для каждой последующей рекурсии, но бывает, что он получает декремент для каждой рекурсии. Вот код: -

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

вход как: -

 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 

и выход: -

2 35 
1 15 
0 10 

0 20 


1 55 
0 50 

0 60 

Так как я прохожу ТТЛ таким образом, что он получает уменьшено только для соответствующих вызовов рекурсии?

Редактировать: - Вопрос также кажется двусмысленным для меня. В нем говорится, что между любой парой узлов будет не более одной (прямой) линии связи. Но, согласно результатам, это предполагает, что график неориентирован.

Редактировать: - Я отредактировал код и подошел с данным выходом. Проблема заключается в том, что узел 35 имеет ребро до 40, а также узел 60. Когда рекурсия идет до 60, она посещает 40, но поскольку ttl> 0, она не печатается. Но поскольку 35 имеет ребро для 40, оно должно быть напечатано. Вот где я застрял.

Answer 1

Кажется, проблема не в ttl. Несмотря на то, должно быть прекращение заявления как

 if(ttl<0) 
      return; 

Но главный вопрос - Поскольку массивы передаются по адресу, посещаемый массив остается модифицирован путем последовательной рекурсией. Таким образом, как только он пытается выполнить итерацию через цикл for, измененный посещенный массив из-за предыдущей рекурсии будет изменен. Предположим, если есть 3 узла, а ребра - 1 2, 1 3, 2 3. Тогда, если мы дадим узлу и ttl равным 1 3, тогда он должен в основном давать как -
1-> 2-> 3,1 -> 3-> 2.
Но в этом случае кода, так как в первом случае 1-> 2-> 3, он уже прошел 3, поэтому посещение [3] становится истинным, заставляя его пропускать 3 в следующей итерации. Таким образом, он дает только 1-> 2-> 3.
Решение вместо массива, вы можете использовать Вектор, заставляя его передавать по значению.