Creating and Printing

Easy
0/40
Average time to solve is 15m
profile
Contributed by
149 upvotes
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
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
4 3
1 2
0 3
2 3
Sample Output 1:
0 3
1 2
2 1 3
3 0 2
Explanation For Sample Input 1:
The graph is shown in the below figure.

graph

So, the neighbour of node 0 is 3. So, in the first line, the first integer is 0 followed by its neighbour 3. Similarly in the second line, 1 is followed by its neighbour 2. 

In the third line, 2 is followed by its neighbours 1 and 3. And in the fourth line, 3 is followed by its neighbours 0 and 2.
Sample Input 2:
3 3
0 1
1 2
2 0
Sample Output 2:
0 1 2
1 0 2
2 0 1
Explanation For Sample Input 2:
The graph is shown in the below figure.

graph

So, the neighbour of node 0 is 1 and 2. So, in the first line, the first integer is 0 followed by its neighbour 1 and 2. Similarly in the second line, 1 is followed by its neighbour 2 and 0. 

In the third line, 2 is followed by its neighbours 1 and 0.
Constraints:
1 <= N <= 5000
1 <= M <= min(5000, (N * (N - 1)) / 2)
0 <= edges[i][0], edges[i][1] <= N-1

Time limit: 1 sec
Hint

Try to store the graph in an array of N nodes and print all its neighbours.

Approaches (1)
Brute Force 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’.
Time Complexity

O(N + M), where N and M denote the number of nodes and the number of edges in the graph, respectively.

 

We are traversing each node and each edge of the graph, so the overall time complexity is O(N + M).

Space Complexity

O(N + M), where N and M denote the number of nodes and the number of edges in the graph, respectively.

 

The graph array and the adjacencyList array both contain a total of N nodes and M edge. So, the overall space complexity is O(N + M).

Code Solution
(100% EXP penalty)
Creating and Printing
Full screen
Console