Skip to Content
CTRL K

Giving Awards

Solución 1

Editorial oficial 

Solución 2

Explicación

Construimos el grafo dirigido con aristas ai→bia_i\to b_i, y llamamos a cada bib_i el vecino de aia_i. Hacer que cada aia_i vaya después de su bib_i en la lista produce una configuración válida, porque bib_i no puede seguir directamente a aia_i si ya está antes que aia_i. Esto siempre es posible, salvo cuando el grafo tiene ciclos. Si hay un ciclo en el grafo, sin embargo, podemos ignorar una arista de un ciclo. Esto sigue siendo válido, porque los ciclos tienen al menos 33 vértices.

Para ver por qué, consideremos este ejemplo: exigimos que el vértice A se coloque antes que B, B antes que C, y C antes que A; de los dos primeros requisitos, A debe estar antes que C con al menos 11 elemento (B) en el medio. Como A y C no son adyacentes, su orden no importa, así que podemos ignorar la tercera arista.

Usamos un DFS en postorden para recorrer todos los nodos; en cada nodo, hacemos DFS de todos sus vecinos antes de imprimir el número del nodo actual. Esto garantiza que todos los vecinos de un vértice aparecen antes que él. Si al recorrer encontramos un ciclo, revisitaríamos un vértice ya visitado, que podemos saltar sin problema, porque ignorar una arista está permitido.

Nótese que, al hacer DFS de cada vértice no visitado en orden, podemos visitar un vecino de algún otro vértice que todavía no visitamos. Sin embargo, esto no es un problema, porque ese otro vértice se recorrerá en un DFS posterior, así que el orden sigue siendo correcto. Su DFS simplemente saltará el vecino ya visitado.

Implementación

Complejidad temporal: O(n+m)\mathcal O(n+m)

// Basado en código de JuanMata en CodeForces
#include <iostream>
#include <vector>
 
using namespace std;
 
const int MAX_N = 30001;
 
vector<int> graph[MAX_N];
bool visited[MAX_N];
 
void dfs(int node) {
	// saltamos si ya está visitado
	if (visited[node]) { return; }
	visited[node] = true;
 
	// visitamos vecinos
	for (auto next : graph[node]) { dfs(next); }
 
	cout << node << ' ';
}
 
int main() {
	int n, m;
	cin >> n >> m;
 
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
	}
 
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) { dfs(i); }
	}
 
	cout << endl;
}
import java.io.*;
import java.util.*;
 
public class GivingAwards {
 
	private static int MAXN = 30001;
	private static List<List<Integer>> graph = new ArrayList<>();
	private static boolean[] visited = new boolean[MAXN];
	private static List<Integer> res = new ArrayList<>();
 
	public static void main(String[] args) throws Exception {
 
		Kattio io = new Kattio();
		int n = io.nextInt();
		int m = io.nextInt();
 
		for (int i = 0; i < MAXN; i++) { graph.add(new ArrayList<>()); }
 
		for (int i = 0; i < m; i++) {
			int u = io.nextInt();
			int v = io.nextInt();
			graph.get(u).add(v);
		}
 
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) { dfs(i); }
		}
 
		for (int i = 0; i < n; i++) { io.print(res.get(i) + " "); }
 
		io.close();
	}
 
	public static void dfs(int node) {
		// saltamos si ya está visitado
		if (visited[node]) { return; }
		visited[node] = true;
		// visitamos vecinos
		for (int next : graph.get(node)) { dfs(next); }
 
		res.add(node);
	}
 
	// BeginCodeSnip{Kattio}
}
Fundamentos