400. Minimum Edges to Reverse for a Source-to-Destination Path

Given a directed graph with n vertices (0-indexed) and m directed edges, a source, and a destination, find the minimum number of edges that need to be reversed so that a directed path exists from source to destination. Print -1 if no amount of reversal can connect them.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains two integers u v, a directed edge. This is followed by a line with the source vertex and a line with the destination vertex. Output: Print a single integer - the minimum number of edges to reverse to connect source to destination, or -1 if impossible.

1 <= n <= 10^5

If destination is unreachable even after allowing EVERY edge to be reversed (i.e., even in the underlying undirected sense), no amount of reversal can ever connect them - this is a fundamentally different kind of failure than simply 'needing more reversals', and correctly maps to printing -1.

Find the minimum number of directed edges that need to be reversed to connect a source to a destination. Brute force: Try every possible SUBSET of edges to reverse and check if source can then reach destination - this is exponential (2^m possible subsets), impractical for large graphs. Optimised: Modeling 'reversal cost' directly as an edge WEIGHT (0 for following the original direction, 1 for reversing) turns this into a standard shortest-path problem - a 0-1 BFS (using a deque instead of a full priority queue) solves it in O(n+m), since there are only two possible edge weights, avoiding the log-factor overhead of a general Dijkstra.

Explore every simple path from source to destination via exhaustive DFS, and for each path count how many of its edges run against the direction of travel (meaning they'd need to be reversed), keeping the minimum such count found over all explored paths. This is correct since it directly evaluates the cost of every possible route, but the number of simple paths in a graph can grow exponentially, making it impractical beyond tiny graphs. Time: O(2^m) Space: O(n + m)

Use the same 0/1-weighted augmented graph, but solve it with 0-1 BFS using a double-ended queue: push the 0-cost original-direction edges to the front of the deque and the 1-cost reversed edges to the back. Because edge weights are restricted to only 0 and 1, the deque naturally stays ordered by distance without any heap operations, finding the identical shortest distance in strictly linear time. Time: O(n + m) Space: O(n + m)

Build an augmented graph where every original directed edge u to v keeps its direction with weight 0, and an extra reverse edge v to u is added with weight 1 (representing the cost of flipping that edge). Running Dijkstra's algorithm from the source on this weighted graph gives a shortest weighted distance to the destination that is exactly the minimum number of edges needing reversal, correctly reducing the problem to single-source shortest paths at the cost of the priority queue's log factor. Time: O((n + m) log n) Space: O(n + m)

1. Build a NEW weighted graph: every original edge u->v ALSO gets a reversed counterpart v->u, where traveling the ORIGINAL direction costs 0 and traveling the REVERSED way costs 1 (since that's the edge you'd actually have to flip). 2. This becomes a shortest-path problem with only TWO distinct edge weights (0 and 1) - a 0-1 BFS (a deque where 0-cost edges push to the FRONT and 1-cost edges push to the BACK) solves it in linear time without needing full Dijkstra. 3. If destination is still unreachable after this search, source and destination aren't even connected in the underlying undirected sense - print -1.

Time: O(n + m) with 0-1 BFS - each vertex and edge is processed a constant number of times. Space: O(n + m), for the doubled edge set (original + reversed) and the deque.

Test source equal to destination (answer 0), a destination that's unreachable even ignoring edge direction (expect -1), and n at the upper bound of 10^5.

Be ready to explain 0-1 BFS clearly as a specialized, faster alternative to Dijkstra specifically for graphs with only two distinct edge weights - pushing 0-cost edges to the FRONT of a deque and 1-cost edges to the BACK maintains the same 'always process the currently-closest vertex next' property Dijkstra needs, without requiring a full priority queue.