# Topological Sort

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

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

CSA | interactive, both versions |

## DFS

Resources | |||
---|---|---|---|

CPH | example walkthrough | ||

CP2 | code | ||

cp-algo | code |

C++

#include <bits/stdc++.h>using namespace std;#define pb push_backint 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 nodesvoid 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 liststatic int N; //number of nodesstatic 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

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

CSES | Easy | ## Show TagsTopoSort | ||||

Kattis | Easy | ## Show TagsTopoSort | ||||

Gold | Easy | ## Show TagsTopoSort | External Sol | |||

Gold | Normal | ## Show TagsTopoSort, Binary Search | External Sol | |||

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

## Give Us Feedback on Topological Sort!

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