# 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 is known as Kahn's Algorithm.

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

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

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

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

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

Gold | Easy | ## Show TagsTopoSort | |||||||

Gold | Normal | ## Show TagsBinary Search, TopoSort | |||||||

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!