Consider n=4, edges: 1→2, 1→3, 2→4, 3→4. Topological order: [1, 2, 3, 4]. Initialize: dp=[1,−∞,−∞,−∞]. Process city 1: Update cities 2 and 3. dp=[1,2,2,−∞]. parent[2] = 1, parent[3] = 1.
Process city 2: Update city 4. dp[4] = max(-Infinity, 2 + 1) = 3. parent[4] = 2. Process city 3: Update city 4. dp[4] = max(3, 2 + 1) = 3. No change. Final: dp[4] = 3. Backtrack: 4→2→1. Reverse: [1, 2, 4].