N cities, M flights (directed, unweighted). Find the longest route from city to city N (most cities visited), or report if impossible.
The graph is a DAG (no cycles). Print the number of cities and the route.
This looks like shortest path but inverted. What technique handles longest paths in DAGs? In general graphs, longest path is NP-hard. But DAGs have no cycles, so you can use dynamic programming. Process nodes in topological order and track the longest path ending at each node.