Reverse a Directed Graph

You are given a directed graph on nodes 0 through n-1 as an adjacency list adj, where adj[u] lists the destinations of edges leaving u (0-indexed, in no particular order, possibly with duplicates for parallel edges). Implement reverse_adj(n, adj) returning the transposed graph: for every occurrence of v in adj[u], the returned adjacency list's entry for v must contain u; each edge u -> v becomes v -> u. Preserve multiplicities: a parallel edge that appears twice in adj[u] must produce two reversed edges. A self-loop u -> u reverses to itself.

Example: reverse_adj(3, {{1,2}, {2}, {}}) (edges 0->1, 0->2, 1->2) returns {{}, {0}, {0,1}}: node 0 has no outgoing edges in the reversed graph (nothing pointed at 0 originally), node 1 gains 0 (since 0->1 reverses to 1->0), and node 2 gains both 0 and 1 (from 0->2 and 1->2).

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

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

Test 04.in reads:

2 0

This is 2 nodes with no edges: the header is the whole test, and the reversed graph is also empty.

Where you'll use it:

• Strongly Connected Components (Kosaraju's algorithm): the algorithm's first pass runs DFS on the reversed graph.
• 2192. All Ancestors of a Node in a Directed Acyclic Graph