Adjacency list Graph representation using vector and pair

Question

I want to implement the adjacency list graph representation from the book competitive programming 1.The implementation uses a vector of V vertices and for each vertex v,another vector that contains pairs of (neighboring vertex and it’s edge weight) that have connection to v.I am having problems to take input of this graph and showing the output.

In the book,they have done such declarations :

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vii;
vector <vii> AdjList;

How should I take input of the following graph as adjacency list and output it's adjacency list representation ? Suppose , every cost of edge is 10.

You already have your answer visually: as a matrix (array[,], array[][]) or a tree structure (node with leafs containing nodes) or an array containing link list elements to represent the arrows from the picture. Have a look at this article. — keenthinker

tejas tejas · Accepted Answer · 2014-08-12T07:17:18

If we want to read graph input in form of n vertices and m edges using graph adjacency implementation.

#include<iostream>
#include<vector>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int main()
{
   int n,m ; 
   cin>>n>>m;
   vector<vii> adjList(n+1); //For vertex 1...n
   //Reading edges for the input for graph
   for(int i=0;i<m;i++)
   {
      int u,v;
      cin>>u>>v;
    /*Here u->v is the edge and pair second term can be used to store weight in
      case of weighted graph.
    */
      adjList[u].push_back(make_pair(v,10));
   }
   //To print the edges stored in the adjacency list
   for(int i=1;i<=n;i++)
   {
       for(int j=0;j<(int)adjList[i].size();j++)
       {
           cout<<"Edge is "<<i<<" -> "<<adjList[i][j].first<<endl;
           cout<<"Weight is "<<adjList[i][j].second<<endl;
       }
   }
   return 0;
}

Adjacency list Graph representation using vector and pair

1 Answers