如果我按以下方式运行代码,它会因输入而崩溃。但是,如果我不使用迭代器并使用注释部分中编写的代码(在 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;
}
最佳答案
问题
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 ++ 标准。
警告
这只能解决最明显的问题。可能还有其他人。我没有检查过。
关于c++ - 如何使用迭代器在 C++ 中的递归函数中传递值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50611492/