c++ - 如何使用迭代器在 C++ 中的递归函数中传递值？

Question

如果我按以下方式运行代码，它会因输入而崩溃。但是，如果我不使用迭代器并使用注释部分中编写的代码(在 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;
}

Answer 1

问题

it 是全局的，因此对 DFS 的每次调用都使用相同的 it。所以当你

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

它“指向”不同的vector 进行迭代。当 DFS 返回时，调用方 DFS 会尝试从错误的 vector 和那个 vector 停止的地方继续已经迭代到 end()。 它 将超出范围递增，一旦发生这种情况，任何使用都是 Undefined Behaviour .此外 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++)

取决于 objective-c ++ 标准。

警告

这只能解决最明显的问题。可能还有其他人。我没有检查过。