Как я могу использовать итератор для передачи значения в рекурсивной функции в C ++? - PullRequest
Новая
       23

Как я могу использовать итератор для передачи значения в рекурсивной функции в C ++?

0 голосов
/ 30 мая 2018

Если я запускаю код, как показано ниже, он падает для входных данных.Но если я не использую итератор и использую код, написанный в разделе комментариев (в функции DFS()), то он работает нормально и больше не падает.Я не могу понять, почему этот код получает сбой итератором.

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<stack>

using namespace std;

vector<pair<int, int> > graph[30009];
vector<pair<int, int> >:: iterator it;

long long int far;
int  visit[30001], last;

void DFS(int vertex, long long int edge)
{
    if(edge > far){
        far = edge;
        last = vertex;
    }
    /*for(int i = 0; i < graph[vertex].size(); i++){
        int node = graph[vertex][i].first;
        int weight = graph[vertex][i].second;
        if(visit[node] == 0){
        visit[node] = 1;
        DFS(node, edge+weight);
    }
}*/
    for(it = graph[vertex].begin(); it != graph[vertex].end(); it++){
        int node = it->first;
        int weight = it->second;
        if(visit[node] == 0){
            visit[node] = 1;
            DFS(node, edge+weight);
        }
    }

return;

}
int main()
{
    int T, n,u,v,w;
    scanf("%d", &T);
    for(int i = 1; i <= T; i++){
            far = 0;

        memset(visit, 0, sizeof(visit));
        scanf("%d", &n);
        for(int j = 0; j < 30001; j++)
            graph[j].clear();
        for(int j = 1; j < n; j++){
            scanf("%d%d%d", &u, &v, &w);
            graph[u].push_back(make_pair(v,w));
            graph[v].push_back(make_pair(u,w));
        }
        visit[0] = 1;
        DFS(0, 0);

        memset(visit, 0, sizeof(visit));
        visit[last] = 1;
        DFS(last, 0);

        printf("Case %d: %lld\n", i, far);
    }
    return 0;
}

1 Ответ

0 голосов
/ 30 мая 2018

Проблема

it является глобальной, поэтому каждый вызов DFS использует один и тот же it.Поэтому, когда вы 

for(it = graph[vertex].begin(); it != graph[vertex].end(); it++){

it "указывает" на другой vector для итерации.Когда DFS возвращается, вызывающий DFS пытается продолжить с того места, на котором остановился, с неправильным vector И это vector уже было повторено до end().it будет увеличен вне диапазона, и как только это произойдет, любое использование будет Неопределенное поведение .Кроме того, it != graph[vertex].end() может быть истинным только при случайной случайности, потому что они оба ссылаются на разные vector с, поэтому петля уходит дальше в неизведанные территории, и в конечном итоге эта ошибка проявляется, во всяком случае, для спрашивающего в аварии.

Решение

Удалить 

vector<pair<int, int> >:: iterator it;

и заменить 

for(it = graph[vertex].begin(); it != graph[vertex].end(); it++)

на 

for(auto it = graph[vertex].begin(); it != graph[vertex].end(); it++)

или 

for(vector<pair<int, int> >::iterator it = graph[vertex].begin(); 
    it != graph[vertex].end(); 
    it++)

в зависимости от целевого стандарта C ++.

Предостережение

Это решает только наиболее заметную проблему.Там могут быть другие.Я не проверял.

...