Grafo (Editorial)

El orden topológico lexicográficamente menor se construye con el algoritmo de Kahn con una cola de prioridad: en cada paso, entre todos los vértices disponibles (vértices en los que no entra ninguna arista proveniente de vértices aún no escritos), se elige el vértice con el número más pequeño.

Una arista añadida $u \to v$ u \to v hace que el vértice $v$ no esté disponible hasta que se escriba el vértice $u$ . Así, añadiendo aristas podemos "esconder" vértices pequeños y obligar de este modo al algoritmo a elegir vértices con números mayores. Cada vértice escondido cuesta una arista del presupuesto $k$ .

La idea voraz. Construimos la respuesta posición a posición. La comparación lexicográfica se decide en la primera posición en que las secuencias difieren, por lo que en cada posición debemos colocar el vértice con el número mayor posible — ninguna ganancia en posiciones posteriores puede compensar una pérdida en la posición actual.

Dividimos los vértices que pueden escribirse en el paso actual en dos conjuntos:

$A$ — los vértices disponibles: todas las aristas que entran en ellos ya han sido "eliminadas". Si no hacemos nada, el algoritmo de Kahn elige el vértice más pequeño de $A$ ;
$B$ — los vértices aplazados. Son vértices que estaban disponibles, pero que decidimos esconder. Para cada uno de ellos nos comprometemos a añadir una arista que entre en él. El origen de esta arista lo elegiremos más tarde — será el vértice escrito inmediatamente antes del aplazado.

El conjunto $A$ se guarda en una cola de prioridad con el elemento más pequeño en la cima (un min-heap), y el conjunto $B$ , en una cola de prioridad con el elemento más grande en la cima (un max-heap).

Cuándo conviene aplazar un vértice. Sea $x$ el vértice más pequeño de $A$ . Si no lo tocamos, en la posición actual se colocará $x$ . Aplazar $x$ (gastando una arista) tiene sentido en dos casos:

$A$ contiene al menos dos vértices. Entonces, tras aplazar $x$ , en la posición actual se colocará el siguiente vértice de $A$ en orden creciente, que es mayor que $x$ ;
$A$ contiene solo el vértice $x$ , pero $B$ contiene un vértice aplazado $y > x$ y > x. Entonces, tras aplazar $x$ , el conjunto $A$ queda vacío, y en la posición actual se colocará el mayor vértice aplazado — un número mayor que $x$ .

En todos los demás casos aplazar no aumenta el número en la posición actual, y no hace falta gastar una arista. Aplazamos los vértices de uno en uno, empezando por el más pequeño, mientras convenga y mientras no se agote el presupuesto $k$ .

Qué vértice escribir. Después de los aplazamientos:

si $A$ no está vacío, escribimos el vértice más pequeño de $A$ — así lo exige la regla del orden lexicográficamente menor;
si $A$ está vacío, escribimos el vértice aplazado más grande $v$ de $B$ y añadimos una arista desde el último vértice escrito hasta $v$ . Es precisamente esta arista la que "escondía" el vértice $v$ : hasta ahora no estaba disponible, y ahora, cuando su nuevo predecesor ya ha sido escrito, se convierte en el único vértice disponible. Los demás vértices aplazados siguen escondidos — sus aristas se añadirán más tarde.

Después, como es habitual en el algoritmo de Kahn, disminuimos los grados de entrada de los vecinos del vértice escrito; los vértices cuyo grado de entrada pasa a ser cero se añaden a $A$ .

Por qué la respuesta es correcta. Todo vértice aplazado tarde o temprano se escribe desde $B$ , y en ese momento se añade exactamente una arista. Por lo tanto, el número de aristas añadidas es igual al número de aplazamientos y no supera $k$ . Todas las aristas añadidas van de un vértice escrito antes a un vértice escrito después, así que el orden hallado es un orden topológico del nuevo grafo y no aparecen ciclos.

Complejidad. Cada vértice entra en $A$ como máximo una vez y en $B$ como máximo una vez, y cada arista del grafo se examina una vez. La complejidad total es $O ((n + m) lo g n)$ O((n + m) \log n).

Algoritmo de resolución del problema

Usamos el algoritmo de Kahn y dos colas de prioridad:

$A$ — min-heap que guarda los vértices disponibles, con el vértice de menor número en la cima.
$B$ — max-heap que guarda los vértices aplazados, con el vértice de mayor número en la cima.

Declaramos los siguientes arrays:

$in d e g [v]$ indeg[v] — el número de aristas entrantes del vértice $v$ que aún no se han procesado;
$an s$ — el orden topológico resultante;
$e d g es$ — la lista de aristas añadidas.

Paso 1. Inicialización

Calcular el grado de entrada de cada vértice.
Añadir a $A$ todos los vértices con grado de entrada cero.
Inicializar $B$ y la lista $e d g es$ como vacíos.

Paso 2. Construcción de la respuesta

Mientras no se hayan procesado los $n$ vértices:

1. Aplazar un vértice si conviene.

Mientras el número de aristas añadidas sea menor que $k$ , el heap $A$ no esté vacío y se cumpla al menos una de las siguientes condiciones:

$A$ contiene al menos dos vértices;
$A$ contiene un único vértice $x$ , y $B$ contiene un vértice $y$ tal que $y > x$ y > x.

Extraer el vértice más pequeño $x$ de $A$ e insertarlo en $B$ . Este vértice se procesará más tarde.

2. Elegir el siguiente vértice.

Si $A$ no está vacío, extraer de él el vértice más pequeño $v$ .
En caso contrario, extraer el vértice más grande $v$ de $B$ . Si $an s$ no está vacío, añadir una arista desde el último vértice de $an s$ hasta $v$ .

Añadir $v$ al final de $an s$ .

3. Actualizar el grafo.

Para cada arista saliente $v \to u$ v \to u:

Disminuir $in d e g [u]$ indeg[u] en uno.
Si $in d e g [u]$ indeg[u] pasa a ser cero, añadir $u$ a $A$ .

Repetir estos pasos hasta que todos los vértices se hayan añadido a $an s$ .

Paso 3. Salida

Imprimir la secuencia $an s$ .
Imprimir el número de aristas añadidas.
Imprimir las propias aristas añadidas.

Ejemplo

Consideremos el ejemplo del enunciado: $n = 5$ n = 5, $k = 2$ k = 2, aristas $1 \to 4$ 1 \to 4, $4 \to 2$ 4 \to 2, $1 \to 3$ 1 \to 3. Grados de entrada iniciales: los vértices $1$ y $5$ tienen grado de entrada $0$ , los vértices $2, 3, 4$ tienen grado de entrada $1$ . Los conjuntos iniciales son $A = {1, 5}$ A = \{1, 5\}, $B = {}$ B = \{\,\}.

Paso	Aplazados	$A$	$B$	$k$	Se toma	Arista	Orden
$1$	$1$ (dos vértices en $A$ )	${5}$	${1}$	$1$	$5$ de $A$	—	$5$
$2$	—	${}$	${1}$	$1$	$1$ de $B$	$5 \to 1$ 5 \to 1	$5, 1$
$3$	$3$ (dos vértices en $A$ : $3$ y $4$ )	${4}$	${3}$	$0$	$4$ de $A$	—	$5, 1, 4$
$4$	— ( $k = 0$ k = 0)	${2}$	${3}$	$0$	$2$ de $A$	—	$5, 1, 4, 2$ 5, 1, 4, 2
$5$	—	${}$	${3}$	$0$	$3$ de $B$	$2 \to 3$ 2 \to 3	$5, 1, 4, 2, 3$ 5, 1, 4, 2, 3

Veamos los pasos con más detalle.

Paso 1. $A = {1, 5}$ A = \{1, 5\} contiene dos vértices, así que aplazamos el más pequeño — $1$ . Ahora $A = {5}$ A = \{5\} contiene un vértice, y $B$ no tiene vértices mayores que $5$ , así que dejamos de aplazar. Escribimos $5$ .
Paso 2. $A$ está vacío. Escribimos el mayor vértice aplazado $1$ y añadimos la arista $5 \to 1$ 5 \to 1. Eliminamos las aristas $1 \to 4$ 1 \to 4 y $1 \to 3$ 1 \to 3: los vértices $4$ y $3$ pasan a estar disponibles, $A = {3, 4}$ A = \{3, 4\}.
Paso 3. $A$ contiene dos vértices — aplazamos $3$ , y el presupuesto de aristas se agota ( $k = 0$ k = 0). Escribimos $4$ , tras lo cual se elimina la arista $4 \to 2$ 4 \to 2 y $A = {2}$ A = \{2\}.
Paso 4. No son posibles más aplazamientos. Escribimos $2$ .
Paso 5. $A$ está vacío. Escribimos el vértice aplazado $3$ y añadimos la arista $2 \to 3$ 2 \to 3.

Obtenemos el orden $5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 y las aristas añadidas $5 \to 1$ 5 \to 1 y $2 \to 3$ 2 \to 3. El grafo original (a la izquierda) y el grafo con las aristas añadidas (a la derecha, las aristas añadidas se muestran en rojo):

Sin aristas añadidas, el orden lexicográficamente menor es $1, 3, 4, 2, 5$ 1, 3, 4, 2, 5: el vértice $5$ no está conectado con nada, pero por su número grande se elige el último. Tras añadir dos aristas, el vértice $5$ pasa a ser el primero, y el orden $5, 1, 4, 2, 3$ 5, 1, 4, 2, 3 es lexicográficamente mayor.

Consideremos un ejemplo más, en el que al principio hay cuatro vértices disponibles. Sean $n = 8, m = 6, k = 4$ n = 8, m = 6, k = 4, y sean las aristas del grafo $6 \to 3, 4 \to 8, 3 \to 5, 1 \to 7, 2 \to 7, 5 \to 7$ 6 \to 3, 4 \to 8, 3 \to 5, 1 \to 7, 2 \to 7, 5 \to 7.

En los vértices $1, 2, 4, 6$ 1, 2, 4, 6 no entra ninguna arista, así que al principio $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $B = {}$ B = \{\,\}. Sin aristas añadidas, el orden lexicográficamente menor es $1, 2, 4, 6, 3, 5, 7, 8$ 1, 2, 4, 6, 3, 5, 7, 8.

El grafo original (a la izquierda) y el grafo tras añadir aristas (a la derecha, las aristas añadidas se muestran en rojo)

Paso	$A$ antes	$B$ antes	$k$	Aplazados	Se toma	Arista
$1$	${1, 2, 4, 6}$ \{1, 2, 4, 6\}	${}$	$4$	$1, 2, 4$	$6$ de $A$	—
$2$	${3}$	${4, 2, 1}$ \{4, 2, 1\}	$1$	$3 (4 > 3)$ 3~(4 > 3)	$4$ de $B$	$6 \to 4$ 6 \to 4
$3$	${8}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$8$ de $A$	—
$4$	${}$	${3, 2, 1}$ \{3, 2, 1\}	$0$	—	$3$ de $B$	$8 \to 3$ 8 \to 3
$5$	${5}$	${2, 1}$	$0$	—	$5$ de $A$	—
$6$	${}$	${2, 1}$	$0$	—	$2$ de $B$	$5 \to 2$ 5 \to 2
$7$	${}$	${1}$	$0$	—	$1$ de $B$	$2 \to 1$ 2 \to 1
$8$	${7}$	${}$	$0$	—	$7$ de $A$	—

Veamos los pasos con más detalle.

Paso 1. $A = {1, 2, 4, 6}$ A = \{1, 2, 4, 6\}, $k = 4$ k = 4. Aplazamos el vértice $1$ , ya que $A$ contiene cuatro vértices, luego $2$ (tres vértices en $A$ ), luego $4$ (dos vértices en $A$ ). El presupuesto baja a $k = 1$ k = 1. Ahora $A = {6}$ A = \{6\} contiene un vértice, y el mayor vértice aplazado $4$ es menor que $6$ — seguir aplazando no conviene. Escribimos $6$ . Se elimina la arista $6 \to 3$ 6 \to 3, y $A = {3}$ A = \{3\}.
Paso 2. $A = {3}$ A = \{3\}, $B = {4, 2, 1}$ B = \{4, 2, 1\}, $k = 1$ k = 1. $A$ contiene un vértice, pero $B$ contiene el vértice $4 > 3$ 4 > 3, así que aplazamos también $3$ ; el presupuesto se agota, $k = 0$ k = 0. $A$ está vacío — escribimos el mayor vértice aplazado $4$ y añadimos la arista $6 \to 4$ 6 \to 4. Se elimina la arista $4 \to 8$ 4 \to 8, y $A = {8}$ A = \{8\}.
Paso 3. No son posibles más aplazamientos. Escribimos $8$ , tras lo cual $A$ queda vacío.
Paso 4. Escribimos el mayor vértice aplazado $3$ y añadimos la arista $8 \to 3$ 8 \to 3. Se elimina la arista $3 \to 5$ 3 \to 5, y $A = {5}$ A = \{5\}.
Paso 5. Escribimos $5$ . Se elimina la arista $5 \to 7$ 5 \to 7, pero en el vértice $7$ aún entran aristas desde $1$ y $2$ , así que $A$ está vacío.
Paso 6. Escribimos el vértice aplazado $2$ y añadimos la arista $5 \to 2$ 5 \to 2. Se elimina la arista $2 \to 7$ 2 \to 7.
Paso 7. Escribimos el vértice aplazado $1$ y añadimos la arista $2 \to 1$ 2 \to 1. Se elimina la arista $1 \to 7$ 1 \to 7, y $A = {7}$ A = \{7\}.
Paso 8. Escribimos $7$ .

La respuesta:

6 4 8 3 5 2 1 7
4
6 4
8 3
5 2
2 1

Este ejemplo muestra claramente todos los casos del algoritmo. En el paso $1$ se aplazan tres vértices de una vez — mientras $A$ contenga al menos dos vértices. En el paso $2$ se aplica la segunda condición: $A$ contiene solo el vértice $3$ , pero $B$ contiene el vértice mayor $4$ , así que $3$ también se aplaza. Los vértices aplazados salen de $B$ en orden decreciente $(4, 3, 2, 1)$ (4, 3, 2, 1), y cada uno de ellos recibe exactamente una arista desde el vértice escrito antes que él. Por tanto, se añaden exactamente tantas aristas como aplazamientos hubo — cuatro.

Implementación del algoritmo

Leemos los datos de entrada. Construimos el grafo. Las listas de adyacencia se guardan en $g$ , y los grados de entrada, en $in d e g$ .

scanf("%d %d %d", &n, &m, &k);
vector<vector<int>> g(n + 1);
vector<int> indeg(n + 1, 0);
for (int i = 0; i < m; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  indeg[v]++;
}

C++

Declaramos dos colas de prioridad: $A$ — los vértices disponibles, con el elemento más pequeño en la cima (un min-heap); $B$ — los vértices aplazados, con el elemento más grande en la cima (un max-heap).

priority_queue<int, vector<int>, greater<int>> A; // disponibles, min-heap
priority_queue<int> B;                            // aplazados, max-heap

Al principio están disponibles todos los vértices con grado de entrada cero.

for (int v = 1; v <= n; v++)
  if (indeg[v] == 0) A.push(v);

El array $or d er$ acumula la respuesta — el orden topológico buscado, y el array $a dd e d$ guarda las aristas añadidas.

vector<int> order;
order.reserve(n);
vector<pair<int, int>> added;

Cada iteración del bucle añade un vértice a la respuesta, hasta que se hayan escrito los $n$ vértices.

while ((int)order.size() < n)
{

Aplazamos vértices. Mientras queden aristas en el presupuesto y el conjunto $A$ no esté vacío, consideramos el menor vértice disponible $x$ . Conviene aplazarlo si $A$ contiene al menos un vértice más o si $B$ contiene un vértice aplazado con un número mayor. El vértice aplazado se traslada de $A$ a $B$ , y el presupuesto $k$ disminuye en $1$ . En caso contrario, los aplazamientos se detienen.

  // aplazamos vertices mientras convenga y queden aristas
  while (k > 0 && !A.empty())
  {
    int x = A.top();
    if (A.size() >= 2 || (!B.empty() && B.top() > x))
    {
      A.pop();
      B.push(x);
      k--;
    }
    else break;
  }

C++

Elegimos el vértice $v$ que se escribirá en la posición actual. Si $A$ no está vacío, es el menor vértice disponible. En caso contrario, tomamos el mayor vértice aplazado y añadimos una arista desde el último vértice escrito $or d er . ba c k ()$ order.back() hasta $v$ .

  int v;
  if (!A.empty())
  {
    v = A.top();
    A.pop();
  }
  else
  {
    v = B.top();
    B.pop();
    added.push_back(make_pair(order.back(), v));
  }

C++

Añadimos $v$ a la respuesta y, como en el algoritmo de Kahn, disminuimos los grados de entrada de sus vecinos. Los vértices cuyo grado de entrada pasa a ser cero quedan disponibles.

  order.push_back(v);
  for (int to : g[v])
    if (--indeg[to] == 0) A.push(to);
}

Imprimimos el orden topológico hallado, el número de aristas añadidas y las propias aristas.

for (int i = 0; i < n; i++)
  printf("%d ", order[i]);
printf("\n%d\n", added.size());
for (auto &e : added)
  printf("%d %d\n", e.first, e.second);