Longest Flight Route - Implementation

Here is the complete solution:

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:
    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

Process in topological order. Track parent for path reconstruction.