我正在用以下给出的对填充向量的邻接列表:
vector<pair<int, int>> adj[1000];
我正在列表上做一个深度搜索,但遇到了一些奇怪的行为。第一个print语句打印一些值,这意味着我在adj[s][0]、adj[s][1]、adj[s][2]等中有一些项。然而,当我计算下一行中adj[s]的大小时,它会打印为零我是不是丢了什么东西?。我对成对向量的定义正确吗?。邻接列表已正确填充,因为当我在dfs中运行
cout << adj[s][0].first << endl;
时,它正确地显示了每个节点的邻居。完整代码
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <utility>
#include <climits>
#include <algorithm>
using namespace std;
vector<pair<int, int>> adj[1000];
bool visited[1000];
int nodeweight[1000];
void initialize()
{
for(int i = 0; i < 1000; i++)
visited[i] = false;
for(int i=0; i < 1000; i++)
adj[i].clear();
for(int i = 0; i <1000; i++)
nodeweight[i] = INT_MAX;
}
void dfs(int s)
{
visited[s] = true;
cout << adj[s][1].first << endl;
int minimum = INT_MAX, tovisit = 0;
for(int i = 0; i < adj[s].size(); i++)
{
cout << adj[s][i].second;
if(!visited[adj[s][i].first] && adj[s][i].second < minimum)
{
minimum = adj[s][i].second;
tovisit = adj[s][i].first;
}
}
nodeweight[tovisit] = minimum;
//dfs(tovisit);
}
int main() {
int N, E;
cin >> N >> E;
while(E--)
{
int i, j, w;
cin >> i >> j >> w;
adj[i].push_back(make_pair(j,w));
adj[j].push_back(make_pair(i,w));
}
initialize();
for(int i = 1; i <= N; i++)
{
dfs(i);
}
return 0;
}
最佳答案
填写adj
后,您将再次清除initialize()
。
首先在adj
中的while
循环中填充main
然后调用initialize()
,其中包括清除其中所有向量的循环:
for(int i=0; i < 1000; i++)
adj[i].clear();
然后在
cout << adj[s][1].first << endl;
中有dfs
这是未定义的行为,因为adj[s]
中没有元素。事实上,您似乎得到了正确的结果,这只是巧合的未定义行为(尽管实际是因为保存矢量数据的内存没有被清除)。adj[s].size()
正确报告为0
。