Implementation - Police Chase - Implement Solution

Here is the complete Dinic implementation:

function dinic(source, sink, capacity):
    flow = 0

    while true:
        // BFS to build level graph
        level = array of size n, all -1
        level[source] = 0
        queue.push(source)
        while queue is not empty:
            u = queue.pop()
            for v in adj[u]:
                if level[v] == -1 and capacity[u][v] > 0:
                    level[v] = level[u] + 1
                    queue.push(v)

        if level[sink] == -1:
            break

        // DFS to find blocking flows
        while true:
            pushed = dfs(source, sink, infinity, level, capacity)
            if pushed == 0:
                break
            flow = flow + pushed

    return flow

function dfs(u, sink, minCap, level, capacity):
    if u == sink:
        return minCap
    for v in adj[u]:
        if level[v] == level[u] + 1 and capacity[u][v] > 0:
            pushed = dfs(v, sink, min(minCap, capacity[u][v]), level, capacity)
            if pushed > 0:
                capacity[u][v] = capacity[u][v] - pushed
                capacity[v][u] = capacity[v][u] + pushed
                return pushed
    return 0

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