Last Updated: 26 Feb, 2021

Creating and Printing

Easy
Asked in company
Ola

Problem statement

You are given an undirected graph of 'N' nodes and 'M' edges. Your task is to create the graph and print the adjacency list of the graph. It is guaranteed that all the edges are unique, i.e., if there is an edge from 'X' to 'Y', then there is no edge present from 'Y' to 'X' and vice versa. Also, there are no self-loops present in the graph.


In graph theory, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.


For Example:
If 'N' = 3 and edges = {{2,1}, {2,0}}.

graph

So, the adjacency list of the graph is stated below.
0 → 2
1 → 2
2 → 0 → 1
Input format:
The first line contains two space-separated integers 'N' and 'M', denoting the total number of nodes and the number of edges, respectively.

Then 'M' lines follow. Each line contains two space-separated integers denoting the nodes that are connected by the current edge.

It is guaranteed that all the edges are unique and there are no self-loops present in the graph.
Output format:
Print the adjacency list of the graph. Total 'N' lines will be printed where 'N' is the number of nodes. 

In each line, the first integer denotes the number of the node, and then the neighbors to this node are printed separated by a single space in ascending order.

You can return any valid adjacency representation of the graph.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.

Approaches

01 Approach

Algorithm:

 

  1. Create an array of size ‘N’ to store the graph. Let’s name this ‘GRAPH’.
  2. Run a loop of ‘i’ from 0 to ‘M’ and do:
    • GRAPH[ EDGES[i][0] ].push_back( GRAPH[EDGES[i][1]] ).
    • GRAPH[ EDGES[i][1] ].push_back( GRAPH[EDGES[i][0]] ).
  3. Create an array ‘ADJACENCYLIST’ of size ‘N’.
  4. Run a loop of ‘i’ from 0 to ‘N’ and do:
    • ADJACENCYLIST[i].push_back( i ).
    • Run a loop of ‘j’ from 0 to ‘GRAPH[i].size’ and do:
      • Insert ‘GRAPH[i][j]’ to the ‘ADJACENCYLIST[i]’.
  5. Finally, return the ‘ADJACENCYLIST’.