jeudi 7 février 2019

Print adjacency list

I've just started with graphs and was printing adjacency list using vector of pairs and unordered_map, though when I test my code against random custom inputs, it matches with the expected results but when I submit it to the online judge it gives me a segmentation fault.

Problem:

Given number of edges 'E' and vertices 'V' of a bidirectional graph. Your task is to build a graph through adjacency list and print the adjacency list for each vertex.

Input:

The first line of input is T denoting the number of testcases.Then first line of each of the T contains two positive integer V and E where 'V' is the number of vertex and 'E' is number of edges in graph. Next, 'E' line contains two positive numbers showing that there is an edge between these two vertex.

Output:

For each vertex, print their connected nodes in order you are pushing them inside the list .

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
int main()
 {
  int T;
  cin>>T;
  while(T--){
  int nv,ne;
  cin>>nv>>ne;
  vector<pair<int,int>> vect;
  for(int i=0;i<ne;i++)
{  int k,l;

    cin>>k>>l;vect.push_back( make_pair(k,l) );    
}
unordered_map<int,vector<int>> umap;
for(int i=0;i<ne;i++)
{
   umap[vect[i].first].push_back(vect[i].second);
    umap[vect[i].second].push_back(vect[i].first);
}
for(int i=0;i<nv;i++)
{
    sort(umap[i].begin(),umap[i].end());
}
int j=0;
for(int i=0;i<nv;i++)
{
   cout<<i<<"->"<<" ";
    for( j=0;j<umap[i].size()-1;j++)
    {
      cout<<umap[i][j]<<"->"<<" ";  
    }
    cout<<umap[i][j];
    cout<<"\n";
}
}
return 0;
}

Example:

Input:

1

5 7

0 1

0 4

1 2

1 3

1 4

2 3

3 4

Output:

0-> 1-> 4

1-> 0-> 2-> 3-> 4

2-> 1-> 3

3-> 1-> 2-> 4

4-> 0-> 1-> 3

Aucun commentaire:

Enregistrer un commentaire