Graph Theory37 sections · 1633 units
Open in Course

Core Idea - Extracting the Cut Edges

(Which roads to block)

After max flow, build the residual graph. Run BFS from s=1s = 1 to find all reachable vertices SS. All other vertices are in TT. The reachability test identifies which side of the cut each vertex is on. For each edge (u,v)(u, v) in the original graph, if uSu \in S and vTv \in T, include it in the minimum cut.

These are the roads to block. Count these edges to verify they match the max flow value. If they do not match, you have made an implementation error.