Build an Adjacency List

intro

Before any BFS/DFS you must build the graph. Implement build_adj(n, edges) for an undirected graph with nodes 0..n-1: for every edge (u, v) push v into adj[u] and u into adj[v], including self-loops, which therefore appear twice in their own list. Do not deduplicate or sort; the checker sorts for you.

Example: build_adj(3, {(0,1), (1,2), (0,0)}) returns adj[0] = {0, 0, 1}, adj[1] = {0, 2}, adj[2] = {1} (sorted for display). The self-loop (0,0) pushes 0 into adj[0] twice: once as "the other endpoint of u" and once as "the other endpoint of v," since u == v.

Input format: each test in tests/*.in is laid out as:

Line 1: n e, the node count and the number of undirected edges; nodes are numbered 0 to n - 1.
Next e lines: u v, one undirected edge between u and v. When e is 0 the file is just the header line.

Test 03.in reads:

This is 3 nodes and 4 edges: the self-loop (0, 0), the edge (0, 1) twice, and (2, 1). Duplicates and self-loops are real edges, so line 1's 4 counts them all.

Where you'll use it:

✦ Solution & editorial unlock with the pass.