c++ - 成对 vector 的大小

Question

我正在用给定的对填充 vector 的邻接列表:

vector<pair<int, int>> adj[1000];

我正在对列表进行深度优先搜索，但遇到了一些奇怪的行为。第一个 print 语句打印一些值，这意味着我在 adj[s][0]、adj[s][1]、adj[s][2] 等中有一些项目。但是，当我在下一行中计算 adj[s] 的大小时，它打印出来的结果为零。我在这里错过了什么吗？我对 vector 对的定义是否正确？邻接表已正确填充，因为当我运行 cout << adj[s][0].first << endl; 时在 dfs 中，它正确地向我展示了每个节点的邻居。

完整代码

#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;
}

Answer 1

您正在清除 adj再次填写initialize() .

首先填写adj在while循环 main .然后你打电话initialize()其中包括这个循环，清除其中的所有 vector :

for(int i=0; i < 1000; i++)
    adj[i].clear();

然后你有cout << adj[s][1].first << endl;在 dfs这是未定义的行为，因为 adj[s] 中没有元素.您似乎得到正确结果的事实只是巧合的未定义行为(尽管实际是因为保存 vector 数据的内存未被清除。)

adj[s].size()被正确报告为 0 .