Graph Theory37 sections · 1633 units
Open in Course

Problem - Police Chase - Read Statement

(CSES 1695)

Read the problem at https://cses.fi/problemset/task/1695. You are given a city with nn intersections and mm bidirectional roads. The police want to prevent criminals from traveling from intersection 11 to intersection nn by blocking roads. Find the minimum number of roads to block and list which roads to block.

Each road can be blocked independently. Notice this is asking for the minimum cut between two vertices. The roads are edges with capacity 11, and you need to find which edges disconnect the source from the sink.