Блог

Главная - Вопросы по программированию - Размер вектора пар

Размер вектора пар

#c #algorithm

#c #алгоритм

Вопрос:

Я заполняю список смежности вектора парами, заданными :

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

Я выполняю поиск в глубину по списку, но испытываю какое-то странное поведение. Первый оператор print выводит некоторое значение, что означает, что у меня есть некоторые элементы в adj [s] [0], adj [s] [1], adj [s] [2] и так далее. Однако, когда я вычисляю размер adj [s] в следующей строке, он выводится равным нулю. Я что-то здесь упускаю?. Правильно ли мое определение для вектора пар?. Список смежности заполнен правильно, потому что, когда я запускал 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] amp;amp; 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;
}

Комментарии:

1. Где находится код, в который вы вставляете элементы adj[][] ? Покажите нам и эту часть.

2. Разве это не должно быть vector<pair<int, int> > adj[1000]; с пробелом между ними > ? Я боюсь, что в противном случае он даже не будет компилироваться

3. Он компилируется правильно. Я также добавил код для вставки в список adj.

4. @PRP начиная с C 11, компиляторы могут распознавать этот новый синтаксис.

5. @ShadKhan Если бы вы опубликовали полный код раньше, вы могли бы получить ответы за считанные секунды 🙂

Ответ №1:

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 .