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

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

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

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.

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

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

BFS

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

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

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

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