Topological Sort
(library/graphs/topological-sort.hpp)

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Include: #include "library/graphs/topological-sort.hpp"

Topological Sort

Functions

• topo_sort(adj): Returns topological ordering given adjacency lists. It will return a list of size less than $n$ if there is no topological ordering.

Resources

• Benq

Verified with

• verify/codeforces/codeforces-1463E.test.cpp

Code

#pragma once

std::vector<int> topo_sort(std::vector<std::vector<int>> adj) {
	int n = (int)adj.size();
	std::vector<int> in(n);
	std::vector<int> res;
	std::list<int> todo;
	for (int i = 0; i < n; i++) {
		for (int j : adj[i]) {
			++in[j];
		}
	}
	for (int i = 0; i < n; i++) {
		if (!in[i]) {
			todo.push_back(i);
		}
	}
	while (!todo.empty()) {
		int x = todo.front();
		todo.pop_front();
		res.push_back(x);
		for (int nxt : adj[x]) {
			if (!(--in[nxt])) {
				todo.push_back(nxt);
			}
		}
	}
	return res;
}

std::vector<int> topo_sort(std::vector<std::vector<int>> adj) {
	int n = (int)adj.size();
	std::vector<int> in(n);
	std::vector<int> res;
	std::list<int> todo;
	for (int i = 0; i < n; i++) {
		for (int j : adj[i]) {
			++in[j];
		}
	}
	for (int i = 0; i < n; i++) {
		if (!in[i]) {
			todo.push_back(i);
		}
	}
	while (!todo.empty()) {
		int x = todo.front();
		todo.pop_front();
		res.push_back(x);
		for (int nxt : adj[x]) {
			if (!(--in[nxt])) {
				todo.push_back(nxt);
			}
		}
	}
	return res;
}

Back to top page