Proper Implementation of graph through adjacency list in c++ stl

Question

I am trying to represent basic undirected graph through adjacency list in STL of C++. Here is my code:

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
   {
       int no_vertices,no_edges;

       printf("Enter the no. of vertices and Edges : ");
       scanf("%d%d",&no_vertices,&no_edges);

       vector<pair<int,int> > graph[no_vertices];
       //Pair because we edge along with its weight!!

       printf("\nEnter the Edges along with their weight :");

       int s,d,weight;

       for(int i=0;i<no_edges;i++)
         {

           scanf("%d%d%d",&s,&d,&weight);
           graph[s].push_back(pair<int,int>(d,weight));

         }

       for(int i=0;i<no_vertices;i++)
          {
            vector<pair<int,int> >::iterator it = graph[i].begin();

            cout<<endl;

            while(it+1!= graph[i].end())
               {
                 printf("%d->",*it);
                 it++;
               }

            printf("%d",*it);

          }

     return 0;
 }

In the above code using I am trying to print each of the vertex along with each of its edge, the compiler prints something and then goes into some memory error or infinite loop.eg. input in above program V=4 E=4 and edges along with the weight are

0 1 4
1 2 5
1 5 2
3 1 3

Expected output-

0->1
1->2->5
2
3->1

but the output is

1
2->5

and then memory error or infinite loop. Please suggest improvements in my code??

–

Thank You!

Answer 1

The main problem is that you don't print the number of the origin vertice (it is not included in graph[i] but it is i itself). The second error is to print *it (a std::pair) instead of it->first (the actual int) as Ashot explained.
One possibility would be to write the last loop like this:

    cout << endl;
    for (int i = 0; i<no_vertices; i++)
    {
        printf("%d", i);
        for (auto& e: graph[i]) {
            printf("->%d", e.first);
        }
        cout << endl;
    }    

Using iterators explicitly:

cout << endl;
for (int i = 0; i<no_vertices; i++)
{
    printf("%d", i);
    vector<pair<int, int> >::iterator it = graph[i].begin();
    vector<pair<int, int> >::iterator it_end = graph[i].end();
    for (; it != it_end; it++) {
        printf("->%d", it->first);
    }
    cout << endl;
}

Although the code above will solve your problem, I probably havn't explained properly why your current code produces an error: As the source node is not a part of the vectors, graph[2] is an empty vector. So you initilize the iterator ìt with graph[2].begin() which is equal to graph[2].end(). As a consequence,

1. the check while(it+1!= graph[2].end()) will always return true (it+1 will start one position BEHIND graph[2].end()).
2. printf("%d->",*it); dereferences an interator pointing to an invalid memory location.

Answer 2

printf("%d->",*it)

This statement is invalid because it has type vector<pair<int,int> >::iterator. So *it has type pair<int,int> and you can't print it using %d which expects int.

Try something like this printf("%d %d",it->first, it->second);