Topological Sort

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

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

Copy
import java.util.*;
import java.io.*;

public class CourseSchedule {
	static List<Integer>[] graph;
	static List<Integer> topo = new ArrayList<Integer>();
	static int N;
	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.

Copy
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool visited[(int)1e5 + 5], on_stack[(int)1e5 + 5];
vector<int> adj[(int)1e5 + 5];
vector<int> cycle;
int N, M;
bool dfs(int n) {

Copy
import java.io.*;
import java.util.*;

public class cycle {
	static List<Integer>[] adj;
	static boolean[] visited, onStack;
	static List<Integer> cycle;
	static int N, M;
	public static void main(String[] args) throws IOException {
		BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));

BFS

The BFS version is known as Kahn's Algorithm.

Copy
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX_N = 100000;

int main()
{
	int n, m;

Copy
public class TopoSort {
	static int[] inDegree;
	static List<Integer>[] edge; // adjacency list

	static int N; // number of nodes

	static void topological_sort() {
		Queue<Integer> q = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			if (inDegree[i] == 0) {

Copy
from collections import deque

# The code is in a function so it can run faster.
def main():
	N, M = map(int, input().split())
	adj = [[] for _ in range(N)]
	for _ in range(M):
		a, b = map(int, input().split())
		a -= 1
		b -= 1

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