BFS Shortest Distances

core

You are given a graph on nodes 0 through n-1 as an adjacency list adj, where adj[u] lists the nodes directly reachable from u by one edge (edges are followed only in the direction given; do not add a reverse edge). Implement bfs_dist(n, adj, src) returning the shortest-path distance in edges from src to every node, using breadth-first search: dist[src] == 0, and any node not reachable from src gets -1. Mark a node as visited the moment it is pushed onto the BFS queue, not when it is popped, so that a node already in the queue (or already processed) is never re-pushed or have its distance changed by a later, longer path.

Example: bfs_dist(4, {{1,2}, {3}, {3}, {}}, 0) (edges 0->1, 0->2, 1->3, 2->3) returns {0, 1, 1, 2}. Node 3 is reached first via whichever of 1 or 2 the BFS processes first, at distance 2; the second path to it is skipped because 3 was already marked visited on its first push.

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.
Last line: s, the start node passed to bfs_dist.

Test 03.in reads:

This is 4 nodes, 2 edges (0 -> 1 and 2 -> 3), starting from node 0. Nodes 2 and 3 are unreachable from 0, so their distances come back -1.

Where you'll use it:

✦ Solution & editorial unlock with the pass.