Longest Flight Route - Core Idea

Finding the longest path in a general graph is NP-hard.

But in a DAG, you can do it in linear time using topological sort. Why?

Because topological order guarantees that when you process node $v$, you have already processed all nodes $u$ that can reach $v$. So you can compute dist[v] = max(dist[u] + 1) for all predecessors $u$.

This is dynamic programming. The state is dist[v] (longest path from source to $v$). The transition is dist[v] = max(dist[v], dist[u] + 1) for each edge $u \to v$. Topological order is what makes this work.