Implementation - Distinct Routes

Here is the path extraction implementation:

function distinctRoutes(n, edges):
    // Build directed flow graph
    capacity = 2D array
    for (u, v) in edges:
        capacity[u][v] = capacity[u][v] + 1

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

    // Extract paths by flow decomposition
    paths = empty list
    flowOnEdge = copy of flow values

    for i from 1 to maxFlow:
        path = [1]
        current = 1

        while current != n:
            for v in adj[current]:
                if flowOnEdge[current][v] > 0:
                    flowOnEdge[current][v] = flowOnEdge[current][v] - 1
                    path.append(v)
                    current = v
                    break

        paths.append(path)

    print maxFlow
    for path in paths:
        print path.length
        print path

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