Dynamic programming 0/49

DP fundamentals: states and transitions · 3 of 3

DP on DAGs

Fill a DP table over a directed acyclic graph in topological order, and rebuild the best route from parent links.

1,905 words · 9 min read

Part 1 of 5 DP on DAGs

DP on a directed acyclic graph

The tables for the frog, the stairs and the coins were filled from left to right, and that worked because each entry only read entries to its left. The frog's figure, repeated below, shows why. Each stone is a circle, each jump is an arrow, and a stone's entry is computed from the stones with arrows into it. Every arrow points right, so going from left to right always fills the start of an arrow before its end.

The frog's first sample. Every arrow points right.

Any DP can be drawn like that. The drawing is called the DP's dependency graph: it has one vertex per state, and an arrow from state uu to state vv whenever the transition for vv reads the value of uu. For the table to be filled, it must have no cycle: a state on a cycle would need its own value before it could be computed, and a recursive function for it would call itself forever. A directed graph without cycles is called a directed acyclic graph (DAG).

An order of the vertices in which every arrow runs from an earlier vertex to a later one is a topological order, and Kahn's algorithm, which the Graphs lesson builds step by step, computes one. In these terms, an evaluation order for a DP is a topological order of its states.

Most DP programs never store this graph or compute that order, because the arrows follow a pattern, such as all pointing right, that a loop follows. For many DPs that make a sequence of choices, the answer is a cheapest or longest path through this graph. The frog's cheapest route, for example, is the cheapest path from stone 0 to the last stone when each arrow costs its jump.

A problem that gives the graph directly

In the next problem the input is the graph itself, and the answer is a longest path. A flight may go from a higher-numbered city to a lower one, so the city numbers are not an order we can rely on, and the program has to find a topological order as it fills the table.

There are nn cities and mm one-way flights, and no sequence of flights returns to a city it has left. Find a route from city 1 to city nn that visits as many cities as possible.

The first input line holds nn and mm, and each of the next mm lines holds a flight aa bb from city aa to city bb. Print the number of cities on the best route, then the cities in order; any best route is accepted. If city nn cannot be reached, print IMPOSSIBLE.

Constraints

  • 2≤n≤1052 \le n \le 10^5
  • 1≤m≤2⋅1051 \le m \le 2 \cdot 10^5
  • 1≤a,b≤n1 \le a, b \le n

Sample · Input

5 5
1 2
2 5
1 3
3 4
4 5

Output

4
1 3 4 5

In the sample, the route 1, 2, 5 visits three cities and the route 1, 3, 4, 5 visits four, so the answer is 4. Listing every route is hopeless at the limits. If each city ii has flights to cities i+1i + 1 and i+2i + 2, the routes from city 1 to city nn are the frog's routes over nn stones, and for n=105n = 10^5 their number has 20,899 digits.

The table needs far less work. The state is a city: let best[v] be the largest number of cities on a route from city 1 to city vv. The last flight of such a route arrives from some city uu, and the part before that flight is a route from city 1 to uu, which has at most best[u] cities. So best[v] is one more than the largest best[u] among the cities uu that have a flight to vv, and city 1 is the base case:

best[1]=1best[v]=1+max⁡u→vbest[u]\begin{aligned} \texttt{best}[1] &= 1 \\ \texttt{best}[v] &= 1 + \max_{u \to v} \texttt{best}[u] \end{aligned}
The sample's flights. Its cities happen to be numbered in a topological order, so every arrow points right. City 5 has two flights into it. The one from city 2 gives 2+1=32 + 1 = 3 cities and the one from city 4 gives 3+1=43 + 1 = 4, which it keeps.

Unreachable cities and the route itself

  • A city that city 1 cannot reach has no route at all, so it must not pass a length on to other cities. The table stores 0 for "no route found". Every real route has at least one city, so 0 cannot be mistaken for a length.
  • The problem asks for the route as well as its length. As with the frog, parent[v] records the city uu whose best[u] gave best[v] its value, and the route is read by following parents back from city nn.