Skip to Content
CTRL K

Orden topológico

Para repasar, un grafo dirigido consiste en aristas que solo se pueden atravesar en una dirección. Además, un grafo acíclico define un grafo que no contiene ciclos, lo que significa que no se puede atravesar una o más aristas y volver al nodo de partida. Juntando estas definiciones, un grafo dirigido acíclico, a veces abreviado como DAG, es un grafo que tiene aristas que solo se pueden atravesar en una dirección y no contiene ciclos.

Orden topológico

HechoFuenteNombreDificultadTagsSolución
CSESCourse ScheduleFácilen el módulo

Un orden topológico  de un grafo dirigido acíclico es un ordenamiento lineal de sus vértices tal que para toda arista dirigida u→vu\to v del vértice uu al vértice vv, uu aparece antes que vv en el ordenamiento.

Hay dos formas habituales de ordenar topológicamente, una que involucra DFS y la otra que involucra BFS.

Recursos
FuenteRecursoNotas
CSATopological Sorting

interactivo, ambas versiones

DFS

Recursos
FuenteRecursoNotas
CPH16.1 - Topological Sort

recorrido de ejemplo

CP24.2.5 - Topological Sort

código

cp-algoTopological Sort

código

#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
vector<int> top_sort;
vector<vector<int>> graph;
vector<bool> visited;
 
void dfs(int node) {
	for (int next : graph[node]) {
		if (!visited[next]) {
			visited[next] = true;
			dfs(next);
		}
	}
	top_sort.push_back(node);
}
 
int main() {
	int n, m;  // La cantidad de nodos y aristas respectivamente
	std::cin >> n >> m;
 
	graph = vector<vector<int>>(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		std::cin >> a >> b;
		graph[a - 1].push_back(b - 1);
	}
 
	visited = vector<bool>(n);
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			dfs(i);
		}
	}
	std::reverse(top_sort.begin(), top_sort.end());
 
	vector<int> ind(n);
	for (int i = 0; i < n; i++) { ind[top_sort[i]] = i; }
 
	// Comprobar si el orden topológico es válido
	bool valid = true;
	for (int i = 0; i < n; i++) {
		for (int j : graph[i]) {
			if (ind[j] <= ind[i]) {
				valid = false;
				goto answer;
			}
		}
	}
answer:;
 
	if (valid) {
		for (int i = 0; i < n - 1; i++) { cout << top_sort[i] + 1 << ' '; }
		cout << top_sort.back() + 1 << endl;
	} else {
		cout << "IMPOSSIBLE" << endl;
	}
}
import java.io.*;
import java.util.*;
 
public class CourseSchedule {
	private static List<Integer>[] graph;
	private static List<Integer> topSort = new ArrayList<>();
	private static boolean[] visited;
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(read.readLine());
		int n = Integer.parseInt(st.nextToken());  // la cantidad de nodos
		int m = Integer.parseInt(st.nextToken());  // y la cantidad de aristas
 
		graph = new ArrayList[n];
		for (int i = 0; i < n; i++) { graph[i] = new ArrayList<>(); }
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(read.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			graph[a].add(b);
		}
 
		visited = new boolean[n];
		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				dfs(i);
			}
		}
		Collections.reverse(topSort);
 
		int[] ind = new int[n];
		for (int i = 0; i < n; i++) { ind[topSort.get(i)] = i; }
 
		// Comprobar si el orden topológico es válido
		boolean valid = true;
	checkSort:
		for (int i = 0; i < n; i++) {
			for (int j : graph[i]) {
				if (ind[j] <= ind[i]) {
					valid = false;
					break checkSort;
				}
			}
		}
 
		if (!valid) {
			System.out.println("IMPOSSIBLE");
		} else {
			StringBuilder ans = new StringBuilder();
			topSort.forEach(node -> ans.append(node + 1).append(' '));
			ans.setLength(ans.length() - 1);
			System.out.println(ans);
		}
	}
 
	private static void dfs(int node) {
		for (int next : graph[node]) {
			if (!visited[next]) {
				visited[next] = true;
				dfs(next);
			}
		}
		topSort.add(node);
	}
}
import sys
 
MAX_N = 10**5
sys.setrecursionlimit(MAX_N)
 
 
def dfs(node: int) -> None:
	for next_ in graph[node]:
		if not visited[next_]:
			visited[next_] = True
			dfs(next_)
	top_sort.append(node)
 
 
# La cantidad de nodos y aristas respectivamente
n, m = map(int, input().strip().split())
graph = [[] for _ in range(n)]
 
for _ in range(m):
	a, b = map(int, input().strip().split())
	graph[a - 1].append(b - 1)
 
visited = [False] * n
top_sort = []
for i in range(n):
	if not visited[i]:
		visited[i] = True
		dfs(i)
top_sort = top_sort[::-1]
 
ind = [0] * n
for i in range(n):
	ind[top_sort[i]] = i
 
# Comprobar si el orden topológico es válido
valid = True
for i in range(n):
	for j in graph[i]:
		if ind[j] <= ind[i]:
			valid = False
			break
 
	if not valid:
		break
 
if valid:
	print(*[i + 1 for i in top_sort])
else:
	print("IMPOSSIBLE")

BFS

La versión con BFS se conoce como algoritmo de Kahn .

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int n, m;
	std::cin >> n >> m;
 
	vector<vector<int>> graph(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		std::cin >> a >> b;
		graph[a - 1].push_back(b - 1);
	}
 
	vector<int> in_degree(n);
	for (const vector<int> &nodes : graph) {
		for (int node : nodes) { in_degree[node]++; }
	}
 
	std::queue<int> queue;
	for (int i = 0; i < n; i++) {
		if (in_degree[i] == 0) { queue.push(i); }
	}
	vector<int> top_sort;
	while (!queue.empty()) {
		int curr = queue.front();
		queue.pop();
		top_sort.push_back(curr);
		for (int next : graph[curr]) {
			if (--in_degree[next] == 0) { queue.push(next); }
		}
	}
 
	if (top_sort.size() == n) {
		for (int i = 0; i < n - 1; i++) { cout << top_sort[i] + 1 << ' '; }
		cout << top_sort.back() + 1 << endl;
	} else {
		cout << "IMPOSSIBLE" << endl;
	}
}
import java.io.*;
import java.util.*;
 
public class CourseSchedule {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(read.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		List<Integer>[] graph = new ArrayList[n];
		for (int i = 0; i < n; i++) { graph[i] = new ArrayList<>(); }
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(read.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			graph[a].add(b);
		}
 
		int[] inDegree = new int[n];
		for (List<Integer> nodes : graph) {
			for (int node : nodes) { inDegree[node]++; }
		}
 
		ArrayDeque<Integer> queue = new ArrayDeque<>();
		List<Integer> topSort = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			if (inDegree[i] == 0) { queue.add(i); }
		}
		while (!queue.isEmpty()) {
			int curr = queue.poll();
			topSort.add(curr);
			for (int next : graph[curr]) {
				if (--inDegree[next] == 0) { queue.add(next); }
			}
		}
 
		if (topSort.size() == n) {
			StringBuilder ans = new StringBuilder();
			topSort.forEach(node -> ans.append(node + 1).append(' '));
			ans.setLength(ans.length() - 1);
			System.out.println(ans);
		} else {
			System.out.println("IMPOSSIBLE");
		}
	}
}
from collections import deque
 
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	graph[a - 1].append(b - 1)
 
in_degree = [0 for _ in range(n)]
for nodes in graph:
	for node in nodes:
		in_degree[node] += 1
 
queue = deque([i for i, in_deg in enumerate(in_degree) if in_deg == 0])
top_sort = []
while queue:
	curr = queue.popleft()
	top_sort.append(curr)
	for next_ in graph[curr]:
		in_degree[next_] -= 1
		if in_degree[next_] == 0:
			queue.append(next_)
 
if len(top_sort) == n:
	print(*[x + 1 for x in top_sort])
else:
	print("IMPOSSIBLE")
Opcional

También podemos usar el algoritmo de Kahn para extraer el orden topológico lexicográficamente mínimo desempateando de forma lexicográfica.

Aunque el código de arriba no hace esto, se puede simplemente reemplazar la queue por una priority_queue para implementar esta extensión.

Encontrar un ciclo

HechoFuenteNombreDificultadTagsSolución
CSESRound Trip IIFácilCycleen el módulo

Podemos modificar el algoritmo de DFS de arriba para devolver un ciclo dirigido en el caso en que no exista un orden topológico. Para hallar el ciclo, agregamos cada nodo que visitamos a la pila hasta detectar un nodo que ya está en la pila.

Por ejemplo, supongamos que nuestra pila actualmente consiste en s1,s2,…,sis_1,s_2,\ldots,s_i y luego visitamos u=sju=s_j para algún j≤ij\le i. Si ese es el caso, entonces sj→sj+1→⋯→si→sjs_j\to s_{j+1}\to \cdots\to s_i\to s_j es un ciclo. Podemos reconstruir el ciclo sin guardar la pila de forma explícita marcando uu como no parte de la pila y retrocediendo de forma recursiva hasta volver a alcanzar uu.

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<vector<int>> graph;
vector<bool> visited, on_stack;
vector<int> cycle;
 
bool dfs(int node) {
	visited[node] = on_stack[node] = true;
	for (int next : graph[node]) {
		if (on_stack[next]) {
			cycle.push_back(node);  // empezar ciclo
			on_stack[node] = on_stack[next] = false;
			return true;
		} else if (!visited[next]) {
			if (dfs(next)) {  // continuar ciclo
				if (on_stack[node]) {
					cycle.push_back(node);
					on_stack[node] = false;
					return true;
				} else {  // se encontró u de nuevo
					cycle.push_back(node);
					return false;
				}
			}
 
			if (!cycle.empty()) {
				return false;  // se terminó el ciclo
			}
		}
	}
 
	on_stack[node] = false;
	return false;
}
 
int main() {
	int n, m;
	cin >> n >> m;
	graph = vector<vector<int>>(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a - 1].push_back(b - 1);
	}
 
	visited = vector<bool>(n);
	on_stack = vector<bool>(n);
	for (int i = 0; cycle.empty() && i < n; i++) { dfs(i); }
 
	if (cycle.empty()) {
		cout << "IMPOSSIBLE" << endl;
	} else {
		reverse(cycle.begin(), cycle.end());
		cout << cycle.size() + 1 << "\n";
		for (int node : cycle) { cout << node + 1 << " "; }
		cout << cycle[0] + 1 << endl;
	}
}
import java.io.*;
import java.util.*;
 
public class RoundTripII {
	private static List<Integer>[] graph;
	private static boolean[] visited, onStack;
	private static List<Integer> cycle = new ArrayList<>();
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(read.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		graph = new ArrayList[n];
		for (int i = 0; i < n; i++) { graph[i] = new ArrayList<>(); }
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(read.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			graph[a].add(b);
		}
 
		visited = new boolean[n];
		onStack = new boolean[n];
		for (int i = 0; cycle.isEmpty() && i < n; i++) { dfs(i); }
 
		if (cycle.isEmpty()) {
			System.out.println("IMPOSSIBLE");
		} else {
			Collections.reverse(cycle);
			System.out.println(cycle.size() + 1);
			for (int node : cycle) { System.out.print((node + 1) + " "); }
			System.out.println(cycle.get(0) + 1);
		}
	}
 
	private static boolean dfs(int node) {
		visited[node] = onStack[node] = true;
		for (int next : graph[node]) {
			if (onStack[next]) {
				cycle.add(node);  // empezar ciclo
				onStack[node] = onStack[next] = false;
				return true;
			} else if (!visited[next]) {
				if (dfs(next)) {  // continuar ciclo
					if (onStack[node]) {
						cycle.add(node);
						onStack[node] = false;
						return true;
					} else {  // se encontró u de nuevo
						cycle.add(node);
						return false;
					}
				}
 
				if (!cycle.isEmpty()) {
					return false;  // se terminó el ciclo
				}
			}
		}
 
		onStack[node] = false;
		return false;
	}
}
import sys
 
MAX_N = 10**5
sys.setrecursionlimit(MAX_N)
 
 
def dfs(node: int) -> bool:
	visited[node] = on_stack[node] = True
	for next_ in graph[node]:
		if on_stack[next_]:
			cycle.append(node)  # empezar ciclo
			on_stack[node] = on_stack[next_] = False
			return True
 
		elif not visited[next_]:
			if dfs(next_):  # continuar ciclo
				if on_stack[node]:
					cycle.append(node)
					on_stack[node] = False
					return True
				else:  # se encontró u de nuevo
					cycle.append(node)
					return False
 
			if cycle:
				return False  # se terminó el ciclo
 
	on_stack[node] = False
	return False
 
 
n, m = map(int, input().strip().split())
graph = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().strip().split())
	graph[a - 1].append(b - 1)
 
visited = [False] * n
on_stack = [False] * n
cycle = []
for i in range(n):
	dfs(i)
	if cycle:
		break
 
if cycle:
	print(len(cycle) + 1)
	print(cycle[0] + 1, *[i + 1 for i in cycle[::-1]])
else:
	print("IMPOSSIBLE")

Programación dinámica

Recursos
FuenteRecursoNotas
CPH16.2 - Dynamic Programming

Una propiedad útil de los grafos dirigidos acíclicos es, como el nombre sugiere, que no existen ciclos. Si consideramos cada nodo del grafo como un estado, podemos hacer programación dinámica sobre el grafo si procesamos los estados en un orden que garantice, para toda arista u→vu\to v, que uu se procesa antes que vv. Por suerte, ¡esa es exactamente la definición de un orden topológico!

HechoFuenteNombreDificultadTagsSolución
CSESLongest Flight RouteFácilen el módulo

En esta tarea, hay que hallar el camino más largo en un DAG.

Solución - Longest Flight Route

Sea dp[v]dp[v] la longitud del camino más largo que termina en el nodo vv. Claramente

dp[v]=max⁡edge u→v existsdp[u]+1, dp[v]=\max_{\text{edge } u\to v \text{ exists}}dp[u]+1,

o 11 si vv es el nodo 11. Si procesamos los estados en orden topológico, está garantizado que dp[u]dp[u] ya se habrá calculado antes de calcular dp[v]dp[v].

Nótese que la implementación de esta idea de abajo usa el algoritmo de Kahn para el orden topológico:

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int city_num, flight_num;
	std::cin >> city_num >> flight_num;
 
	vector<vector<int>> flights(city_num);
	vector<vector<int>> back_edge(city_num);
	for (int i = 0; i < flight_num; i++) {
		int a, b;
		std::cin >> a >> b;
		flights[--a].push_back(--b);
		back_edge[b].push_back(a);
	}
 
	// Usar el algoritmo de Kahn para hacer un orden topológico
	vector<int> in_degree(city_num);
	for (const vector<int> &nodes : flights) {
		for (int node : nodes) { in_degree[node]++; }
	}
 
	std::queue<int> queue;
	for (int i = 0; i < city_num; i++) {
		if (in_degree[i] == 0) { queue.push(i); }
	}
	vector<int> top_sort;
	while (!queue.empty()) {
		int curr = queue.front();
		queue.pop();
		top_sort.push_back(curr);
		for (int next : flights[curr]) {
			if (--in_degree[next] == 0) { queue.push(next); }
		}
	}
 
	// Calcular el arreglo dist en orden topológico
	vector<int> parent(city_num, -1);
	vector<int> dist(city_num, INT32_MIN);
	dist[0] = 1;
	for (int i = 0; i < top_sort.size(); i++) {
		int b = top_sort[i];
		for (int prev : back_edge[b]) {
			if (dist[prev] + 1 > dist[b]) {
				dist[b] = dist[prev] + 1;
				parent[b] = prev;
			}
		}
	}
 
	if (dist[city_num - 1] < 0) {
		cout << "IMPOSSIBLE" << endl;
	} else {
		// dist[city_num - 1] denota la longitud del camino más largo
		// que termina en la ciudad final. p. ej. Lehmälä
		cout << dist[city_num - 1] << endl;
 
		// Empezar desde la ciudad final, seguir el puntero parent
		// para construir el camino entero hacia atrás
		int at = city_num - 1;
		vector<int> route;
		while (parent[at] != -1) {
			route.push_back(at);
			at = parent[at];
		}
		route.push_back(0);
 
		// Imprimir la ruta en el orden correcto
		std::reverse(route.begin(), route.end());
		for (int i = 0; i < route.size() - 1; i++) { cout << route[i] + 1 << ' '; }
		cout << route.back() + 1 << endl;
	}
}
import java.io.*;
import java.util.*;
 
public class LongestFlight {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(read.readLine());
		int cityNum = Integer.parseInt(st.nextToken());
		int flightNum = Integer.parseInt(st.nextToken());
 
		List<Integer>[] flights = new ArrayList[cityNum];
		List<Integer>[] backEdge = new ArrayList[cityNum];
		for (int i = 0; i < cityNum; i++) {
			flights[i] = new ArrayList<>();
			backEdge[i] = new ArrayList<>();
		}
		for (int i = 0; i < flightNum; i++) {
			st = new StringTokenizer(read.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			flights[a].add(b);
			backEdge[b].add(a);
		}
 
		// Usar el algoritmo de Kahn para hacer un orden topológico
		int[] inDegree = new int[cityNum];
		for (List<Integer> nodes : flights) {
			for (int node : nodes) { inDegree[node]++; }
		}
 
		ArrayDeque<Integer> queue = new ArrayDeque<>();
		List<Integer> topSort = new ArrayList<>();
		for (int i = 0; i < cityNum; i++) {
			if (inDegree[i] == 0) { queue.add(i); }
		}
		while (!queue.isEmpty()) {
			int curr = queue.poll();
			topSort.add(curr);
			for (int next : flights[curr]) {
				if (--inDegree[next] == 0) { queue.add(next); }
			}
		}
 
		// Calcular el arreglo dist en orden topológico
		int[] parent = new int[cityNum];
		Arrays.fill(parent, -1);
		int[] dist = new int[cityNum];
		Arrays.fill(dist, Integer.MIN_VALUE);
		dist[0] = 1;
		for (int i = 0; i < topSort.size(); i++) {
			int b = topSort.get(i);
			for (int prev : backEdge[b]) {
				if (dist[prev] + 1 > dist[b]) {
					dist[b] = dist[prev] + 1;
					parent[b] = prev;
				}
			}
		}
 
		if (dist[cityNum - 1] < 0) {
			System.out.println("IMPOSSIBLE");
		} else {
			// dist[city_num - 1] denota la longitud del camino más largo
			// que termina en la ciudad final. p. ej. Lehmälä
			System.out.println(dist[cityNum - 1]);
 
			// Empezar desde la ciudad final, seguir el puntero parent
			// para construir el camino entero hacia atrás
			int at = cityNum - 1;
			List<Integer> route = new ArrayList<>();
			while (parent[at] != -1) {
				route.add(at);
				at = parent[at];
			}
			route.add(0);
 
			// Imprimir la ruta en el orden correcto
			Collections.reverse(route);
			StringBuilder ans = new StringBuilder();
			for (int i = 0; i < route.size() - 1; i++) {
				ans.append(route.get(i) + 1).append(' ');
			}
			ans.append(route.get(route.size() - 1) + 1);
			System.out.println(ans);
		}
	}
}
from collections import deque
 
city_num, flight_num = list(map(int, input().split(" ")))
flights = [[] for _ in range(city_num)]
back_edge = [[] for _ in range(city_num)]
for _ in range(flight_num):
	a, b = list(map(int, input().split(" ")))
	a, b = a - 1, b - 1
	flights[a].append(b)
	back_edge[b].append(a)
 
# Usar el algoritmo de Kahn para hacer un orden topológico
in_degree = [0] * city_num
for nodes in flights:
	for node in nodes:
		in_degree[node] += 1
 
queue = deque([i for i, in_deg in enumerate(in_degree) if in_deg == 0])
top_sort = []
while queue:
	curr = queue.popleft()
	top_sort.append(curr)
	for next_ in flights[curr]:
		in_degree[next_] -= 1
		if in_degree[next_] == 0:
			queue.append(next_)
 
# Calcular el arreglo dist en orden topológico
parent = [-1] * city_num
dist = [-float("inf")] * city_num
dist[0] = 1
for i in range(len(top_sort)):
	b = top_sort[i]
	for prev in back_edge[b]:
		if dist[prev] + 1 > dist[b]:
			dist[b] = dist[prev] + 1
			parent[b] = prev
 
if dist[city_num - 1] == -float("inf"):
	print("IMPOSSIBLE")
else:
	# dist[city_num - 1] denota la longitud del camino más largo
	# que termina en la ciudad final. p. ej. Lehmälä
	print(dist[city_num - 1])
 
	# Empezar desde la ciudad final, seguir el puntero parent
	# para construir el camino entero hacia atrás
	at = city_num - 1
	route = []
	while parent[at] != -1:
		route.append(at)
		at = parent[at]
	route.append(0)
 
	# Imprimir la ruta en el orden correcto
	print(*[c + 1 for c in route[::-1]])

Problemas

HechoFuenteNombreDificultadTagsSolución
CSES★ Game RoutesFácilTopoSortSolución
Kattis★ Quantum SuperpositionFácilTopoSortSolución
GoldTimelineFácilTopoSortSolución
CFSubstringFácilTopoSortSolución
CFFox and NamesFácilTopoSortSolución
CFDirecting EdgesFácilTopoSort—
GoldMilking OrderNormalTopoSort, Binary SearchSolución
CFPattern MatchingNormalTopoSort, BitmasksSolución
CSES★ Course Schedule IIDifícilTopoSortSolución
AC★ Constrained Topological SortDifícilTopoSortSolución
Union-Find / conjuntos disjuntos (DSU)Orden topológico