Ordenación Topológica (Editorial)

Un orden topológico de un grafo dirigido es una ordenación de sus vértices tal que para cada arista $u \to v$ u \to v el vértice $u$ aparece en la secuencia antes que el vértice $v$ . Un orden topológico existe si y solo si el grafo no contiene ciclos dirigidos (es decir, es acíclico).

Resolvemos el problema mediante la búsqueda en profundidad. A cada vértice se le asigna un color:

blanco — el vértice aún no ha sido visitado;
gris — el vértice ha sido visitado, pero su procesamiento no ha terminado (está en la pila de recursión actual);
negro — el vértice y todos los vértices alcanzables desde él han sido procesados por completo.

Inicialmente todos los vértices son blancos. Iniciamos una búsqueda en profundidad desde cada vértice blanco. Al entrar en un vértice lo coloreamos de gris; al salir de él lo coloreamos de negro y en ese momento lo añadimos a una lista. El orden de los vértices en el orden topológico es el inverso del orden en que se vuelven negros: el primer vértice procesado por completo será el último en el orden, y el último vértice procesado será el primero.

Detección de ciclos. Si durante el recorrido encontramos una arista que lleva a un vértice gris, el grafo contiene un ciclo y el orden topológico es imposible — imprimimos $- 1$ .

Complejidad. Cada vértice y cada arista se procesan exactamente una vez, por lo que el tiempo de ejecución es $O (n + m)$ O(n + m).

Ejemplo

El grafo del ejemplo tiene la siguiente forma:

Junto a cada vértice $v$ colocamos las etiquetas $d [v] / f [v]$ d[v] / f[v], donde $d [v]$ es el instante en que comienza el procesamiento del vértice y $f [v]$ es el instante en que termina su procesamiento. Los vértices ordenados topológicamente se disponen en orden decreciente de los valores $f [v]$ .

Implementación del algoritmo

Como el número de vértices del grafo es grande, almacenamos el grafo como una lista de adyacencia $g$ . Para llevar el control del estado de los vértices usamos el array $u se d$ :

$u se d [i] = 0$ used[i] = 0, si el vértice $i$ aún no ha sido visitado (el vértice es blanco);
$u se d [i] = 1$ used[i] = 1, si el vértice $i$ ha sido visitado, pero su procesamiento aún no ha terminado (el vértice es gris);
$u se d [i] = 2$ used[i] = 2, si el vértice $i$ ha sido procesado (el vértice es negro);

Durante la ejecución de la búsqueda en profundidad añadimos los vértices al array $t o p$ en el orden en que termina su procesamiento. Al finalizar el algoritmo, el array $t o p$ contendrá los vértices en el orden inverso al orden topológico.

vector<vector<int> > g;
vector<int> used, top;

La función dfs realiza una búsqueda en profundidad a partir del vértice $v$ .

void dfs(int v)
{

Entramos en el vértice $v$ y lo marcamos de gris.

  used[v] = 1;

Recorremos todos los vértices $t o$ alcanzables desde el vértice $v$ .

  for (int to : g[v])
  {

Si la arista dirigida $(v, t o)$ (v, to) lleva a un vértice gris, el grafo contiene un ciclo. En este caso asignamos $f l a g = 1$ flag = 1.

    if (used[to] == 1) flag = 1;

Si el vértice $t o$ aún no ha sido visitado, iniciamos recursivamente una búsqueda en profundidad desde él.

    if (used[to] == 0) dfs(to);
  }

Terminamos el procesamiento del vértice $v$ . Lo marcamos de negro y lo añadimos al final del array $t o p$ .

  used[v] = 2;
  top.push_back(v);
}

La parte principal del programa. Leemos los datos de entrada y construimos la lista de adyacencia del grafo.

scanf("%d %d",&n,&m);
g.resize(n+1); used.resize(n+1);

for(i = 0; i < m; i++)
{
  scanf("%d %d",&a,&b);
  g[a].push_back(b);
}

C++

Realizamos una búsqueda en profundidad sobre el grafo dirigido.

flag = 0;
for(i = 1; i <= n; i++)
  if (used[i] == 0) dfs(i);

Si durante la búsqueda en profundidad se detectó un ciclo ( $f l a g = 1$ flag = 1), imprimimos $- 1$ .

if (flag == 1) printf("-1");
else

En caso contrario, imprimimos los vértices del grafo en el orden inverso al de su inserción en el array $t o p$ .

  for(i = top.size() - 1; i >= 0; i--)
    printf("%d ",top[i]);

printf("\n");

Implementación del algoritmo — Kahn

Almacenamos el grafo de entrada en la lista de adyacencia $g$ .

Los grados de entrada de los vértices se almacenan en el array $I n D e g r ee$ InDegree.

El resultado del orden topológico se almacena en el array $t o p$ .

vector<vector<int> > g;
vector<int> InDegree, top;
deque<int> q;

Leemos el número de vértices $n$ y el número de aristas $m$ .

scanf("%d %d",&n,&m);
g.resize(n+1);
InDegree.resize(n+1);

Leemos las $m$ aristas del grafo.

for(i = 0; i < m; i++)
{
  scanf("%d %d",&a,&b);
  g[a].push_back(b);

Para cada arista $(a, b)$ aumentamos $I n D e g r ee [b]$ InDegree[b] en $1$ .

  InDegree[b]++;
}

Todos los vértices con grado de entrada cero se añaden a la cola $q$ .

for(i = 1; i < InDegree.size(); i++)
  if (!InDegree[i]) q.push_back(i);

Continuamos el algoritmo mientras la cola $q$ no esté vacía.

while(!q.empty())
{

Extraemos de la cola el vértice $v$ y lo añadimos al final de la lista del orden topológico.

  v = q.front(); q.pop_front();
  top.push_back(v);

Eliminamos del grafo las aristas $(v, t o)$ (v, to). Para cada una de ellas disminuimos el grado de entrada del vértice $t o$ .

  for (int to : g[v])
  {
    InDegree[to]--;

Si el grado de entrada del vértice $t o$ se vuelve cero, lo añadimos a la cola. Más adelante se colocará en la lista del orden topológico.

    if (!InDegree[to]) q.push_back(to);
  }
}

Si no todos los $n$ vértices se han añadido al array $t o p$ , el grafo contiene un ciclo y el orden topológico es imposible.

if (top.size() < n) 
  printf("-1\n");
else
{

En caso contrario, imprimimos los vértices del grafo en orden topológico.

  for (int x : top) printf("%d ", x);
  printf("\n");
}

Implementación en Java — búsqueda en profundidad

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

public class Main
{
  static ArrayList<ArrayList<Integer>> g;
  static ArrayList<Integer> top = new ArrayList<Integer>();
  static int used[];
  static int n, m, flag = 0;
    
  static void dfs(int v)
  {
    used[v] = 1;
    for(int i = 0; i < g.get(v).size(); i++)
    {
      int to = g.get(v).get(i);
      if (used[to] == 1) flag = 1;
      if (used[to] == 0) dfs(to);
    }
    used[v] = 2;
    top.add(v);
  }
    
  public static void main(String[] args)
  {
    FastScanner con = new FastScanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    g = new ArrayList<ArrayList<Integer>>();
    used = new int[n+1];
      
    for (int i = 0; i <= n; i++)
      g.add(new ArrayList<Integer>());

    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();     
      g.get(a).add(b);
    }
      
    for(int i = 1; i <= n; i++)
      if (used[i] == 0) dfs(i);
      
    if (flag == 1) System.out.println("-1");
    else
      for(int i = top.size() - 1; i >= 0; i--)
        System.out.print(top.get(i) + " ");
    System.out.println();
  }
}	

class FastScanner
{
  BufferedReader br;
  StringTokenizer st;
 
  public FastScanner(InputStream inputStream)
  {
    br = new BufferedReader(new InputStreamReader(inputStream));
    st = new StringTokenizer("");
  }
 
  public String next()
  {
    while (!st.hasMoreTokens())
    {
      try
      {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e)
      {
        return null;
      }
    }
    return st.nextToken();
  }
 
  public int nextInt()
  {
    return Integer.parseInt(next());
  }
}

Java

Implementación en Java — Kahn

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

public class Main
{
  static ArrayList<ArrayList<Integer>> g;
  static ArrayList<Integer> top;
  static int InDegree[];
  static int n, m, flag = 0;
  
  public static void main(String[] args)
  {
    FastScanner con = new FastScanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    g = new ArrayList<ArrayList<Integer>>();
    InDegree = new int[n+1];
      
    for (int i = 0; i <= n; i++)
      g.add(new ArrayList<Integer>());

    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();     
      g.get(a).add(b);
      InDegree[b]++;
    }
      
    Queue<Integer> q = new LinkedList<Integer>();
    for(int i = 1; i <= n; i++)
      if (InDegree[i] == 0) q.add(i);

    top = new ArrayList<Integer>();
    while (!q.isEmpty())
    {
      int v = q.poll();
      top.add(v);
      for (int to : g.get(v))
      {
        InDegree[to]--;
        if (InDegree[to] == 0) q.add(to);
      }
    }

    if (top.size() < n)
    	System.out.println("-1");
      else
      {
        for (int x : top) System.out.print(x + " ");
        System.out.println();
      }
  }
}	

class FastScanner
{
  BufferedReader br;
  StringTokenizer st;
 
  public FastScanner(InputStream inputStream)
  {
    br = new BufferedReader(new InputStreamReader(inputStream));
    st = new StringTokenizer("");
  }
 
  public String next()
  {
    while (!st.hasMoreTokens())
    {
      try
      {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e)
      {
        return null;
      }
    }
    return st.nextToken();
  }
 
  public int nextInt()
  {
    return Integer.parseInt(next());
  }
}

Java

Implementación en Python — búsqueda en profundidad

Aumentamos la profundidad máxima de recursión.

import sys
sys.setrecursionlimit(10000)

La función dfs realiza una búsqueda en profundidad a partir del vértice $v$ .

def dfs(v):

Entramos en el vértice $v$ y lo marcamos de gris.

  used[v] = 1

Recorremos todos los vértices $t o$ alcanzables desde el vértice $v$ .

  for to in g[v]:

Si la arista dirigida $(v, t o)$ (v, to) lleva a un vértice gris, el grafo contiene un ciclo. En este caso asignamos $f l a g = 1$ flag = 1.

    if used[to] == 1:
      global flag
      flag = 1

Si el vértice $t o$ aún no ha sido visitado, iniciamos recursivamente una búsqueda en profundidad desde él.

    if used[to] == 0:
      dfs(to)

Terminamos el procesamiento del vértice $v$ . Lo marcamos de negro y lo añadimos al final del array $t o p$ .

  used[v] = 2
  top.append(v)

La parte principal del programa. Leemos el número de vértices $n$ y el número de aristas $m$ .

n, m = map(int, input().split())

Almacenamos el grafo de entrada en la lista de adyacencia $g$ . Declaramos la lista $u se d$ .

g = [[] for _ in range(n + 1)]
used = [0] * (n + 1)

Leemos la lista de aristas y construimos la lista de adyacencia del grafo.

for _ in range(m):
  a, b = map(int, input().split())
  g[a].append(b)

Realizamos una búsqueda en profundidad sobre el grafo dirigido.

flag = 0
top = []
for i in range(1, n + 1):
  if used[i] == 0: dfs(i)

Si durante la búsqueda en profundidad se detectó un ciclo ( $f l a g = 1$ flag = 1), imprimimos $- 1$ .

if flag == 1:
  print("-1")
else:

En caso contrario, imprimimos los vértices del grafo en el orden inverso al de su inserción en el array $t o p$ .

  for i in range(len(top) - 1, -1, -1):
    print(top[i], end=" ")
  print()

Implementación en Python — Kahn

Declaramos la cola $q$ .

from collections import deque
q = deque()

Leemos el número de vértices $n$ y el número de aristas $m$ .

n, m = map(int, input().split())

Almacenamos el grafo de entrada en la lista de adyacencia $g$ .

Los grados de entrada de los vértices se almacenan en la lista $I n D e g r ee$ InDegree.

El resultado del orden topológico se almacena en la lista $t o p$ .

g = [[] for _ in range(n + 1)]
InDegree = [0] * (n + 1)
top = []

Leemos las $m$ aristas del grafo.

for _ in range(m):
  a, b = map(int, input().split())
  g[a].append(b)

Para cada arista $(a, b)$ aumentamos $I n D e g r ee [b]$ InDegree[b] en $1$ .

  InDegree[b] += 1

Todos los vértices con grado de entrada cero se añaden a la cola $q$ .

for i in range(1, len(InDegree)):
  if not InDegree[i]: q.append(i)

Continuamos el algoritmo mientras la cola $q$ no esté vacía.

while q:

Extraemos de la cola el vértice $v$ y lo añadimos al final de la lista del orden topológico.

  v = q.popleft()
  top.append(v)

Eliminamos del grafo las aristas $(v, t o)$ (v, to). Para cada una de ellas disminuimos el grado de entrada del vértice $t o$ .

  for to in g[v]:
    InDegree[to] -= 1

Si el grado de entrada del vértice $t o$ se vuelve cero, lo añadimos a la cola. Más adelante se colocará en la lista del orden topológico.

    if not InDegree[to]: q.append(to)

Si no todos los $n$ vértices se han añadido al array $t o p$ , el grafo contiene un ciclo y el orden topológico es imposible.

if len(top) < n:
  print("-1")
else:

En caso contrario, imprimimos los vértices del grafo en orden topológico.

  for i in top:
    print(i, end=" ")
  print()