PrevNext
Rare
 0/10

Topological Sort

Authors: Benjamin Qi, Nathan Chen

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

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

Edit This Page

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→vu\to v from vertex uu to vertex vv, uu comes before vv 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

Resources
CPH
16.1 - Topological Sort

example walkthrough

CP2
4.2.5 - Topological Sort

code

cp-algo
Topological Sort

code

C++

#include <bits/stdc++.h>
using namespace std;


#define pb push_back


int N;                                // Number of nodes
vector<int> graph[100000], top_sort;  // Assume that this graph is a DAG
bool visited[100000];


void dfs(int node) {

Java

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


public class CourseSchedule {
	static List<Integer>[] graph;
	static List<Integer> topo = new ArrayList<Integer>();
	static int N;
	static boolean[] visited;
	public static void main(String[] args) throws Exception {
		BufferedReader br =

Python

import sys


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




def dfs(node):
	for i in graph[node]:
		if not visited[i]:
			visited[i] = True

Finding a Cycle

Round Trip II
CSES - Easy

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

We can modify the 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 s1,s2,…,sis_1,s_2,\ldots,s_i and we then visit u=sju=s_j for some j≤ij\le i. Then sj→sj+1→⋯→si→sjs_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 by marking uu as not part of the stack and recursively backtracking until uu is reached again.

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;


bool visited[(int)1e5 + 5], on_stack[(int)1e5 + 5];
vector<int> adj[(int)1e5 + 5];
vector<int> cycle;
int N, M;
bool dfs(int n) {

Java

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


public class cycle {
	static List<Integer>[] adj;
	static boolean[] visited, onStack;
	static List<Integer> cycle;
	static int N, M;
	public static void main(String[] args) throws IOException {
		BufferedReader sc =

Python

import sys


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




def dfs(node):
	visited[node], on_stack[node] = True, True
	for u in adj[node]:
		if on_stack[u]:

Warning!

This code assumes that there are no self-loops.

BFS

The BFS version is known as Kahn's Algorithm.

C++

Course Schedule Solution

#include <iostream>
#include <queue>
#include <vector>
using namespace std;


const int MAX_N = 100000;


int main() {
	int n, m;
	cin >> n >> m;

Java

public class TopoSort {
	static int[] inDegree;
	static List<Integer>[] edge;  // adjacency list


	static int N;  // number of nodes


	static void topological_sort() {
		Queue<Integer> q = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			if (inDegree[i] == 0) { q.add(i); }

Python

from collections import deque


# The code is in a function so it can run faster.
def main():
	N, M = map(int, input().split())
	adj = [[] for _ in range(N)]
	for _ in range(M):
		a, b = map(int, input().split())
		a -= 1
		b -= 1

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.

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→vu\to v that uu is processed before vv. 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

Problems

StatusSourceProblem NameDifficultyTags
CSES
Game Routes
Easy
Show TagsTopoSort
Kattis
Quantum Superposition
Easy
Show TagsTopoSort
Gold
Timeline
Easy
Show TagsTopoSort
CF
Substring
Easy
Show TagsTopoSort
CF
Fox and Names
Easy
Show TagsTopoSort
Gold
Milking Order
Normal
Show TagsBinary Search, TopoSort
CSES
Course Schedule II
Hard
Show TagsTopoSort

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
PrevNext