Graph Theory37 sections · 1633 units
Open in Course

Police Chase - Extracting the Cut

(BFS on residual graph)

After computing max flow with capacity 11 on all edges, do a BFS or DFS from node 11 on the residual graph. Mark all reachable nodes. The min-cut consists of edges (u,v)(u,v) where uu is reachable and vv is not.

Collect these edges and output them. The number of such edges equals the max flow value (the minimum number of roads to block). These are the edges you need to remove to disconnect the criminal from escape.