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

Question

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

Я пытаюсь решить проблему Узел слишком далеко, как указано в 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

и вывод:

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

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

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

0

c++depth-first-search graph onlinejudge recursion

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Кажется, проблема не в 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, заставляя его передавать по значению.

0