Topological Sort DFS BFS Finding a Cycle Dynamic Programming Solution - Longest Flight Route Problems

Rare

0/13

Topological Sort

Authors: Benjamin Qi, Nathan Chen

Contributors: Michael Cao, Andi Qu, Andrew Wang, Qi Wang, Maggie Liu, Martin Lin

Ordering the vertices of a directed acyclic graph such that each vertex is visited before its children.

Edit This Page

Prerequisites

Topological Sort DFS BFS Finding a Cycle Dynamic Programming Solution - Longest Flight Route Problems

To review, a directed graph consists of edges that can only be traversed in one direction. Additionally, an acyclic graph defines a graph which does not contain cycles, meaning you are unable to traverse across one or more edges and return to the node you started on. Putting these definitions together, a directed acyclic graph, sometimes abbreviated as DAG, is a graph which has edges which can only be traversed in one direction and does not contain cycles.

Topological Sort

Course Schedule

CSES - Easy

Focus Problem – try your best to solve this problem before continuing!

A topological sort of a directed acyclic graph is a linear ordering of its vertices such that for every directed edge $u\to v$ from vertex $u$ to vertex $v$ , $u$ comes before $v$ in the ordering.

There are two common ways to topologically sort, one involving DFS and the other involving BFS.

Resources
		CSA	Topological Sorting	interactive, both versions

DFS


CPH	16.1 - Topological Sort	example walkthrough
CP2	4.2.5 - Topological Sort	code
cp-algo	Topological Sort	code

C++

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

vector<int> top_sort;
vector<vector<int>> graph;

Java

import java.io.*;
import java.util.*;

public class CourseSchedule {
	private static List<Integer>[] graph;
	private static List<Integer> topSort = new ArrayList<>();
	private static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

Python

import sys

MAX_N = 10**5
sys.setrecursionlimit(MAX_N)


def dfs(node: int) -> None:
	for next_ in graph[node]:
		if not visited[next_]:
			visited[next_] = True

BFS

The BFS version is known as Kahn's Algorithm.

C++

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {

Java

import java.io.*;
import java.util.*;

public class CourseSchedule {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(read.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

Python

from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	graph[a - 1].append(b - 1)

in_degree = [0 for _ in range(n)]
for nodes in graph:

Pro Tip

If the length of the array containing the end order does not equal the number of elements that need to be sorted, then there is a cycle in the graph.

Optional

We can also use Kahn's algorithm to extract the lexicographically minimum topological sort by breaking ties lexographically.

Although the above code does not do this, one can simply replace the queue with a priority_queue to implement this extension.

Finding a Cycle

Round Trip II

CSES - Easy

Focus Problem – try your best to solve this problem before continuing!

We can modify the DFS algorithm above to return a directed cycle in the case where a topological sort does not exist. To find the cycle, we add each node we visit onto the stack until we detect a node already on the stack.

For example, suppose that our stack currently consists of $s_1,s_2,\ldots,s_i$ and we then visit $u=s_j$ for some $j\le i$ . If that's the case, then $s_j\to s_{j+1}\to \cdots\to s_i\to s_j$ is a cycle. We can reconstruct the cycle without explicitly storing the stack b marking $u$ as not part of the stack and recursively backtracking until $u$ is reached again.

Warning!

This code assumes that there are no self-loops, i.e. no edges from a node to itself.

C++

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited, on_stack;
vector<int> cycle;

Java

import java.io.*;
import java.util.*;

public class RoundTripII {
	private static List<Integer>[] graph;
	private static boolean[] visited, onStack;
	private static List<Integer> cycle = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

Python

import sys

MAX_N = 10**5
sys.setrecursionlimit(MAX_N)


def dfs(node: int) -> bool:
	visited[node] = on_stack[node] = True
	for next_ in graph[node]:
		if on_stack[next_]:

Dynamic Programming

Resources
		CPH	16.2 - Dynamic Programming

One useful property of directed acyclic graphs is, as the name suggests, that no cycles exist. If we consider each node in the graph as a state, we can perform dynamic programming on the graph if we process the states in an order that guarantees for every edge $u\to v$ that $u$ is processed before $v$ . Fortunately, this is the exact definition of a topological sort!

Longest Flight Route

CSES - Easy

Focus Problem – try your best to solve this problem before continuing!

In this task, we must find the longest path in a DAG.

Solution - Longest Flight Route

Let $dp[v]$ denote the length of the longest path ending at the node $v$ . Clearly

dp[v]=\max_{\text{edge } u\to v \text{ exists}}dp[u]+1,

or $1$ if $v$ is node $1$ . If we process the states in topological order, it is guaranteed that $dp[u]$ will already have been computed before computing $dp[v]$ .

Note that the implementation of this idea below uses Kahn's algorithm for topological sorting:

C++

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {

Java

import java.io.*;
import java.util.*;

public class LongestFlight {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(read.readLine());
		int cityNum = Integer.parseInt(st.nextToken());
		int flightNum = Integer.parseInt(st.nextToken());

Python

from collections import deque

city_num, flight_num = list(map(int, input().split(" ")))
flights = [[] for _ in range(city_num)]
back_edge = [[] for _ in range(city_num)]
for _ in range(flight_num):
	a, b = list(map(int, input().split(" ")))
	a, b = a - 1, b - 1
	flights[a].append(b)
	back_edge[b].append(a)

Problems

Source	Problem Name	Difficulty	Tags
CSES	Game Routes	Easy	Show Tags TopoSort
Kattis	Quantum Superposition	Easy	Show Tags TopoSort
Gold	Timeline	Easy	Show Tags TopoSort
CF	Substring	Easy	Show Tags TopoSort
CF	Fox and Names	Easy	Show Tags TopoSort
CF	Directing Edges	Easy	Show Tags TopoSort
Gold	Milking Order	Normal	Show Tags Binary Search, TopoSort
CF	Pattern Matching	Hard	Show Tags Bitwise, TopoSort
CSES	Course Schedule II	Hard	Show Tags TopoSort
AC	Constrained Topological Sort	Hard	Show Tags TopoSort

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum

Table of Contents

Topological Sort

Prerequisites

Table of Contents

Topological Sort

DFS

BFS

Pro Tip

Optional

Finding a Cycle

Warning!

Dynamic Programming

Solution - Longest Flight Route

Problems

Module Progress:

Join the USACO Forum!

Table of Contents

Topological Sort

Prerequisites

Table of Contents

Topological Sort

DFS

BFS

Pro Tip

Optional

Finding a Cycle

Warning!

Dynamic Programming

Solution - Longest Flight Route

Problems

Module Progress:Not Started

Join the USACO Forum!

Module Progress: