Как передать непрерывно убывающую переменную в рекурсии? [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

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

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

Редактировать:- Я редактировал код и придумал данный вывод. Проблема в том, что узел 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.
Решение вместо массива, вы можете использовать Vector, заставляя его передавать по значению.