Implementation - Police Chase

Here is the min-cut extraction implementation:

function policeChase(n, edges):
    // Build bidirectional flow graph
    capacity = 2D array of size n x n, all 0
    for (u, v) in edges:
        capacity[u][v] = capacity[u][v] + 1
        capacity[v][u] = capacity[v][u] + 1

    // Run max flow from 1 to n
    maxFlow = dinic(1, n, capacity)

    // Find reachable set from source in residual graph
    reachable = array of size n, all false
    queue.push(1)
    reachable[1] = true
    while queue is not empty:
        u = queue.pop()
        for v from 1 to n:
            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]) or (reachable[v] and not reachable[u]):
            cutEdges.append((u, v))

    print maxFlow
    print cutEdges

Time: $O(V^2 E)$. Space: $O(V + E)$.