PreviousNext
Coding/Graphs and trees

Minimum edge reversals

Write codeMedium25 min

Your task

You are given a directed graph with n nodes (0..n-1) and edges [u, v]. You may travel along an edge in its given direction for free, or traverse it against its direction by paying 1 (reversing that edge). Return the minimum number of edge reversals needed to get from src to dst, or -1 if dst is unreachable even with reversals. Assume 1 <= n <= 100000; a 0-1 BFS in O(V+E) is the intended solution.

Examples

min_edge_reversals(n: int, edges: list[list[int]], src: int, dst: int) -> int
Example 1
Inputmin_edge_reversals(4, [[0, 1], [1, 2], [3, 2]], 0, 3)
Output1