Adjacency List - Graph Representation
One of the most popular ways of representing graphs is with adjacency lists. An adjacency list is a way of representing a graph as an array of lists. Each element of the array represents a vertex in the graph, and the list associated with that vertex contains the vertices that are adjacent to it.
Given the directed graph in the picture, we can obtain its adjacency list:
g = [
[], # We skip vertex 0
[2, 4], # Vertex 1
[5], # Vertex 2
[2], # Vertex 3
[], # Vertex 4
[6, 8], # Vertex 5
[4, 7], # Vertex 6
[8], # Vertex 7
[5], # Vertex 8
]
As you can notice, the graph representation with an adjacency list is way more compact compared to the adjacency matrix. This is due to the fact that there aren’t that many edges in our graph. In some cases, when the number of edges is large enough, it might be more efficient to store the graph in an adjacency matrix.
Challenge: Edges to Adjacency List
Given an undirected graph with
v vertices and e edges, you are asked to obtain its adjacency list.Input
The first line of the input contains two integers
v (1 ≤ v ≤ 100 000) and e (1 ≤ e ≤ 100 000).The following
e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.Output
The program should print the adjacency list of the given graph. Each row should start with the id of a vertex followed by a semicolon (
:) and then its connections. The connections on each row should be separated by a space. The order of both the vertices and the connections can be arbitrary.Examples
Input | Output |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 1: 2 4
2: 1 3 5
3: 2
4: 1 6
5: 2 6 8
6: 4 7 5
7: 8 6
8: 5 7 |
Explanation
Constraints
Time limit: 2.2 seconds
Memory limit: 512 MB
Output limit: 1 MB