Guide to Competitive Programming

An important class of graphs are directed acyclic graphs, also called DAGs. Such graphs do not contain cycles, and many problems are easier to solve if wemay assume that this is the case. In particular, we can always construct a topological sort for the graph and then apply dynamic programming.

Topological Sorting:

A topological sort is an ordering of the nodes of a directed graph such that if there is a path from node a to node b, then node a appears before node b in the ordering.

For example, one possible topological sort is [4, 1, 5, 2, 3, 6].

A directed graph has a topological sort exactly when it is acyclic. If the graph contains a cycle, it is not possible to form a topological sort, because no node of the cycle can appear before the other nodes of the cycle in the ordering. It turns out that depth-first search can be used to both check if a directed graph contains a cycle and, if it does not, to construct a topological sort.

Topological Sorting

The idea is to go through the nodes of the graph and always begin a depth-first search at the current node if it has not been processed yet. During the searches, the nodes have three possible states:

  • state 0: the node has not been processed (white)
  • state 1: the node is under processing (light gray)
  • state 2: the node has been processed (dark gray)

Initially, the state of each node is 0. When a search reaches a node for the first time, its state becomes 1. Finally, after all edges from the node have been processed, its state becomes 2.

If the graph contains a cycle, we will discover this during the search, because sooner or later we will arrive at a node whose state is 1. In this case, it is not possible to construct a topological sort. If the graph does not contain a cycle, we can construct a topological sort by adding each node to a list when its state becomes 2. Finally, we reverse the list and get a topological sort for the graph.

Now we are ready to construct a topological sort for our example graph. The first search proceeds from node 1 to node 6, and adds nodes 6, 3, 2, and 1 to the list. Then, the second search proceeds from node 4 to node 5 and adds
nodes 5 and 4 to the list. The final reversed list is [4, 5, 1, 2, 3, 6], which corresponds to a topological sort. Note that a topological sort is not unique; there can be several topological sorts for a graph.

Shows a graph that does not have a topological sort. During the search, we reach node 2 whose state is 1, which means that the graph contains a cycle. Indeed, there is a cycle 2 → 3 → 5 → 2.

graph topological sort

Dynamic Programming:

Using dynamic programming, we can efficiently answer many questions regarding paths in directed acyclic graphs. Examples of such questions are:

  • What is the shortest/longest path from node a to node b?
  • How many different paths are there?
  • What is the minimum/maximum number of edges in a path?
  • Which nodes appear in every possible path?

Note that many of the above problems are difficult to solve or not well-defined for general graphs.

As an example, consider the problem of calculating the number of paths from node a to node b. Let paths(x) denote the number of paths from node a to node x. As a base case, paths(a) = 1. Then, to calculate other values of paths(x), we can use the recursive formula paths(x) = paths(s1) + paths(s2) + ·· ·+paths(sk ), where s1, s2, . . . , sk are the nodes from which there is an edge to x. Since the graph is acyclic, the values of paths can be calculated in the order of a topological sort.

Shows the values of paths in an example scenario where we want to calculate the number of paths from node 1 to node 6. For example, paths(6) = paths(2) + paths(3), because the edges that end at node 6 are 2 → 6 and 3 → 6.

Since paths(2) = 2 and paths(3) = 2, we conclude that paths(6) = 4. The paths are as follows:

  • 1 → 2 → 3 → 6
  • 1 → 2 → 6
  • 1 → 4 → 5 → 2 → 3 → 6
  • 1 → 4 → 5 → 2 → 6

Processing Shortest Paths Dynamic programming can also be used to answer questions regarding shortest paths in general (not necessarily acyclic) graphs. Namely, if we know minimum distances from a starting node to other nodes (e.g., after using Dijkstra’s algorithm), we can easily create a directed acyclic shortest paths graph that indicates for each node the possible ways to reach the node using a shortest path from the starting node. For example, Fig. 7.30 shows a graph and the corresponding shortest paths graph.

shortest paths graph

Coin Problem Revisited In fact, any dynamic programming problem can be represented as a directed acyclic graph where each node corresponds to a dynamic programming state and the edges indicate how the states depend on each other.
For example, consider the problem of forming a sum of money n using coins {c1, c2, . . . , ck } (Sect. 6.1.1). In this scenario, we can construct a graph where each node corresponds to a sum of money, and the edges show how the coins can be chosen. For example, shows the graph for the coins {1, 3, 4} and n = 6.

Using this representation, the shortest path from node 0 to node n corresponds to a solution with the minimum number of coins, and the total number of paths from node 0 to node n equals the total number of solutions.