Here is the min-cut implementation:
function policeChase(n, m, edges):
// Build graph with capacity 1
capacity = 2D array of size n x n, all 0
adj = adjacency list
for (u, v) in edges:
capacity[u][v] = 1
capacity[v][u] = 1
adj[u].append(v)
adj[v].append(u)
// Run max flow
edmondsKarp(n, 1, n, capacity, adj)
// BFS to find reachable nodes from source
reachable = array of size n, all false
queue.push(1)
reachable[1] = true
while queue is not empty:
u = queue.pop()
for v in adj[u]:
if not reachable[v] and capacity[u][v] > 0:
reachable[v] = true
queue.push(v)
// Find cut edges
cutEdges = empty list
for (u, v) in edges:
if reachable[u] and not reachable[v]:
cutEdges.append((u, v))
else if reachable[v] and not reachable[u]:
cutEdges.append((v, u))
print cutEdges.size
print cutEdges
Time: . Space: .