Longest Flight Route - Implementation

Pattern: DP on DAG for longest path.

function longestFlightRoute(n, adj):
    topoOrder = topologicalSort(adj)
    dp = array of size n + 1, all -infinity
    parent = array of size n + 1, all -1
    dp[1] = 1

    for u in topoOrder:
        if dp[u] == -infinity:
            continue
        for v in adj[u]:
            if dp[u] + 1 > dp[v]:
                dp[v] = dp[u] + 1
                parent[v] = u

    if dp[n] == -infinity:
        print "IMPOSSIBLE"
    else:
        print dp[n]
        path = reconstructPath(parent, n)
        print path

Time: $O(N + M)$. Space: $O(N)$.