Rare
0/8

# Topological Sort

Authors: Benjamin Qi, Michael Cao, Nathan Chen, Andi Qu, Andrew Wang

### Prerequisites

An ordering of vertices in a directed acyclic graph that ensures that a node is visited before every node it has a directed edge to.

To review, a directed graph consists of edges that can only be traversed in one direction. Additionally, a 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

Focus Problem – read through 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
CSAinteractive, both versions

## DFS

Resources
CPHexample walkthrough
CP2code
cp-algocode

C++

#include <bits/stdc++.h>using namespace std;
#define pb push_back
int N; // Number of nodesvector<int> graph[100000], top_sort; // Assume that this graph is a DAGbool visited[100000];
void dfs(int node) {

Java

import java.util.*;import java.io.*;
public class CourseSchedule {    public static ArrayList <Integer> g[];    public static ArrayList <Integer> topo = new ArrayList < Integer > ();    public static int N;    public static boolean visited[];    public static void main(String[] args) throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

### Finding a Cycle

Focus Problem – read through 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 $s_1,s_2,\ldots,s_i$ and we then visit $u=s_j$ for some $j\le i$. 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 by marking $u$ as not part of the stack and recursively backtracking until $u$ is reached again.

C++

#include <vector>#include <iostream>#include <algorithm>using namespace std;
bool visited[(int)10e5+5], on_stack[(int)10e5+5];vector<int> adj[(int)10e5+5];vector<int> cycle;int N, M;bool dfs(int n) {

Java

import java.io.*;import java.util.*;
public class cycle {    public static ArrayList < Integer > [] adj;    public static boolean visited[], on_stack[];    public static ArrayList < Integer > cycle;    public static int N, M;    public static void main(String[] args) throws IOException {        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));

### Warning!

This code assumes that there are no self-loops.

## BFS

The BFS version, known as Kahn's Algorithm, makes it obvious how to extract the lexicographically minimum topological sort.

C++

int in_degree[100000];vector<int> edge[100000];
int N; //number of nodes
void compute() {    queue<int> q;    for (int i = 0; i < N; i++) {        if (in_degree[i] == 0) {            q.push(i);

Java

static int in_degree[];static ArrayList<Integer> edge[]; //adjacency list
static int N; //number of nodes
static void topological_sort() {    Queue<Integer> q = new ArrayDeque<Integer>();    for (int i = 0; i < N; i++) {        if (in_degree[i] == 0) {            q.add(i);

## Dynamic Programming

Resources
CPH

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!

Focus Problem – read through this problem before continuing!

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

Solution

## Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESEasy
Show Tags

TopoSort

KattisEasy
Show Tags

TopoSort

GoldEasy
Show Tags

TopoSort

External Sol
GoldNormal
Show Tags

TopoSort, Binary Search

External Sol
CSESHard
Show Tags

TopoSort

### 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!

## Give Us Feedback on Topological Sort!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.