Shad Khan Shad Khan - 2 months ago 22
C++ Question

Size of a vector of pairs

I am filling up an adjacency list of vector with pairs given by :

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


I am doing a depth first search on the list but experiencing some weird behaviour. The first print statement prints some value which means I have some items in adj[s][0], adj[s][1], adj[s][2] and so on. However when I calculate the size of adj[s] in the next line it prints out to be zero. Am I missing something here?. Is my definition for vector of pairs correct?. The adjacency list is correctly filled because when I ran
cout << adj[s][0].first << endl;
in dfs, it was correctly showing me the neighbors of each and every node.

Complete code

#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

You are clearing adj again after filling in initialize().