Walkthrough Example

Consider $n = 4$, edges: $1 \to 2$, $1 \to 3$, $2 \to 4$, $3 \to 4$. Topological order: [$1$, $2$, $3$, $4$]. Initialize: $dp = [1, -\infty, -\infty, -\infty]$. Process city $1$: Update cities $2$ and $3$. $dp = [1, 2, 2, -\infty]$. 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 \to 2 \to 1$. Reverse: [$1$, $2$, $4$].