Topological Sort

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

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.

DFS

1#include <bits/stdc++.h>
2using namespace std;
3
4#define pb push_back
5
6int N; // Number of nodes
7vector<int> graph[100000], top_sort; // Assume that this graph is a DAG
8bool visited[100000];
9
10void dfs(int node) {

1import java.util.*;
2import java.io.*;
3
4public class CourseSchedule {
5    public static ArrayList <Integer> g[];
6    public static ArrayList <Integer> topo = new ArrayList < Integer > ();
7    public static int N;
8    public static boolean visited[];
9    public static void main(String[] args) throws Exception {
10        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

Finding a Cycle

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,\dots ,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.

1#include <vector>
2#include <iostream>
3#include <algorithm>
4using namespace std;
5
6bool visited[(int)10e5+5], on_stack[(int)10e5+5];
7vector<int> adj[(int)10e5+5];
8vector<int> cycle;
9int N, M;
10bool dfs(int n) {

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

BFS

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

1int in_degree[100000];
2vector<int> edge[100000];
3
4int N; //number of nodes
5
6void compute() {
7    queue<int> q;
8    for (int i = 0; i < N; i++) {
9        if (in_degree[i] == 0) {
10            q.push(i);

1static int in_degree[];
2static ArrayList<Integer> edge[]; //adjacency list
3
4static int N; //number of nodes
5
6static void topological_sort() {
7    Queue<Integer> q = new ArrayDeque<Integer>();
8    for (int i = 0; i < N; i++) {
9        if (in_degree[i] == 0) {
10            q.add(i);

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!

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

Problems