Componentes fuertemente conexas y grafo de condensación

Definiciones

Sea $G=(V,E)$ un grafo dirigido con vértices $V$ y aristas $E \subseteq V \times V$. Denotamos con $n=|V|$ el número de vértices y con $m=|E|$ el número de aristas en $G$. Es fácil extender todas las definiciones de este artículo a multigrafos, pero no nos centraremos en eso.

Un subconjunto de vértices $C \subseteq V$ se llama componente fuertemente conexa si se cumplen las siguientes condiciones:

• para todos $u,v\in C$, si $u \neq v$ existe un camino de $u$ a $v$ y un camino de $v$ a $u$, y
• $C$ es maximal, en el sentido de que no se puede agregar ningún vértice sin violar la condición anterior.

Denotamos con $\text{SCC}(G)$ el conjunto de componentes fuertemente conexas de $G$. Estas componentes fuertemente conexas no se intersectan entre sí y cubren todos los vértices del grafo. Así, el conjunto $\text{SCC}(G)$ es una partición de $V$.

Consideremos este grafo $G_\text{example}$, en el que se destacan las componentes fuertemente conexas:

Aquí tenemos $\text{SCC}(G_\text{example})={{0,7},{1,2,3,5,6},{4,9},{8}}.$ Podemos confirmar que, dentro de cada componente fuertemente conexa, todos los vértices son alcanzables entre sí.

Definimos el grafo de condensación $G^{\text{SCC}}=(V^{\text{SCC}}, E^{\text{SCC}})$ de la siguiente forma:

• los vértices de $G^{\text{SCC}}$ son las componentes fuertemente conexas de $G$; es decir, $V^{\text{SCC}} = \text{SCC}(G)$, y
• para todos los vértices $C_i,C_j$ del grafo de condensación, hay una arista de $C_i$ a $C_j$ si y solo si $C_i \neq C_j$ y existen $a\in C_i$ y $b\in C_j$ tales que hay una arista de $a$ a $b$ en $G$.

El grafo de condensación de $G_\text{example}$ se ve así:

La propiedad más importante del grafo de condensación es que es acíclico. En efecto, no hay ‘bucles’ en el grafo de condensación por definición, y si hubiera un ciclo que pasara por dos o más vértices (componentes fuertemente conexas) del grafo de condensación, entonces, por alcanzabilidad, la unión de estas componentes fuertemente conexas tendría que ser una sola componente fuertemente conexa: contradicción.

El algoritmo descrito en la sección siguiente encuentra todas las componentes fuertemente conexas en un grafo dado. Después de eso se puede construir el grafo de condensación.

Algoritmo de Kosaraju

Descripción del algoritmo

El algoritmo descrito fue propuesto de forma independiente por Kosaraju y Sharir alrededor de 1980. Se basa en dos series de búsqueda en profundidad, con un tiempo de ejecución de $O(n + m)$.

En el primer paso del algoritmo, realizamos una secuencia de búsquedas en profundidad (dfs), visitando el grafo entero. Es decir, mientras queden vértices no visitados, tomamos uno de ellos e iniciamos una búsqueda en profundidad desde ese vértice. Para cada vértice, registramos el tiempo de salida $t_\text{out}[v]$. Esta es la ‘marca de tiempo’ en la que termina la ejecución de dfs sobre el vértice $v$, es decir, el momento en el que todos los vértices alcanzables desde $v$ han sido visitados y el algoritmo está de vuelta en $v$. El contador de marcas de tiempo no debe reiniciarse entre llamadas consecutivas a dfs. Los tiempos de salida juegan un papel clave en el algoritmo, lo que quedará claro cuando discutamos el siguiente teorema.

Primero, definimos el tiempo de salida $t_\text{out}[C]$ de una componente fuertemente conexa $C$ como el máximo de los valores $t_\text{out}[v]$ para todo $v \in C.$ Además, en la demostración del teorema, mencionaremos el tiempo de entrada $t_{\text{in}}[v]$ para cada vértice $v\in G$. El número $t_{\text{in}}[v]$ representa la ‘marca de tiempo’ en la que se llama a la función recursiva dfs sobre el vértice $v$ en el primer paso del algoritmo. Para una componente fuertemente conexa $C$, definimos $t_{\text{in}}[C]$ como el mínimo de los valores $t_{\text{in}}[v]$ para todo $v \in C$.

El teorema demostrado es muy importante para encontrar componentes fuertemente conexas. Significa que cualquier arista en el grafo de condensación va de una componente con un valor mayor de $t_\text{out}$ a una componente con un valor menor.

Si ordenamos todos los vértices $v \in V$ en orden decreciente de su tiempo de salida $t_\text{out}[v]$, entonces el primer vértice $u$ pertenecerá a la componente fuertemente conexa “raíz”, que no tiene aristas entrantes en el grafo de condensación. Ahora queremos ejecutar algún tipo de búsqueda desde este vértice $u$ de modo que visite todos los vértices de su componente fuertemente conexa, pero no otros vértices. Haciéndolo de forma repetida, podemos ir encontrando todas las componentes fuertemente conexas: eliminamos todos los vértices que pertenecen a la primera componente encontrada, luego encontramos el siguiente vértice restante con el mayor valor de $t_\text{out}$, y ejecutamos esta búsqueda desde él, y así sucesivamente. Al final, habremos encontrado todas las componentes fuertemente conexas. Para encontrar un método de búsqueda que se comporte como queremos, consideramos el siguiente teorema:

Se omite la demostración (pero es directa). Como consecuencia de este teorema, no habrá aristas desde la componente “raíz” hacia las demás componentes en el grafo de condensación de $G^T$. Así, para visitar toda la componente fuertemente conexa “raíz” que contiene al vértice $v$, podemos simplemente ejecutar una búsqueda en profundidad desde el vértice $v$ en el grafo transpuesto $G^T$. Esto visitará precisamente todos los vértices de esta componente fuertemente conexa. Como se mencionó antes, luego podemos eliminar estos vértices del grafo. Después, encontramos el siguiente vértice con un valor maximal de $t_\text{out}[v]$, y ejecutamos la búsqueda en el grafo transpuesto empezando desde ese vértice para encontrar la siguiente componente fuertemente conexa. Repitiendo esto, encontramos todas las componentes fuertemente conexas.

Así, en resumen, discutimos el siguiente algoritmo para encontrar componentes fuertemente conexas:

• Paso 1. Ejecutar una secuencia de búsquedas en profundidad sobre $G$, que producirá alguna lista (p. ej. order) de vértices, ordenados por tiempo de salida creciente $t_\text{out}$.

• Paso 2. Construir el grafo transpuesto $G^T$, y ejecutar una serie de búsquedas en profundidad sobre los vértices en orden inverso (es decir, en orden decreciente de tiempos de salida). Cada búsqueda en profundidad producirá una componente fuertemente conexa.

• Paso 3 (opcional). Construir el grafo de condensación.

La complejidad temporal del algoritmo es $O(n + m)$, porque la búsqueda en profundidad se realiza dos veces. Construir el grafo de condensación también es $O(n+m).$

Finalmente, es apropiado mencionar el orden topológico aquí. En el paso 1, encontramos los vértices en el orden de tiempo de salida creciente. Si $G$ es acíclico, esto corresponde a un orden topológico (invertido) de $G$. En el paso 2, el algoritmo encuentra las componentes fuertemente conexas en orden decreciente de sus tiempos de salida. Así, encuentra componentes - vértices del grafo de condensación - en un orden que corresponde a un orden topológico del grafo de condensación.

Implementación

vector<bool> visited; // registra qué vértices ya están visitados

// ejecuta búsqueda en profundidad empezando en el vértice v.
// cada vértice visitado se agrega al vector de salida cuando dfs sale de él.
void dfs(int v, vector<vector<int>> const& adj, vector<int> &output) {
    visited[v] = true;
    for (auto u : adj[v])
        if (!visited[u])
            dfs(u, adj, output);
    output.push_back(v);
}

// entrada: adj -- lista de adyacencia de G
// salida: components -- las componentes fuertemente conexas en G
// salida: adj_cond -- lista de adyacencia de G^SCC (por vértices raíz)
void strongly_connected_components(vector<vector<int>> const& adj,
                                  vector<vector<int>> &components,
                                  vector<vector<int>> &adj_cond) {
    int n = adj.size();
    components.clear(), adj_cond.clear();

    vector<int> order; // lista de vértices de G ordenada por tiempo de salida

    visited.assign(n, false);

    // primera serie de búsquedas en profundidad
    for (int i = 0; i < n; i++)
        if (!visited[i])
            dfs(i, adj, order);

    // crear lista de adyacencia de G^T
    vector<vector<int>> adj_rev(n);
    for (int v = 0; v < n; v++)
        for (int u : adj[v])
            adj_rev[u].push_back(v);

    visited.assign(n, false);
    reverse(order.begin(), order.end());

    vector<int> roots(n, 0); // da el vértice raíz de la SCC de un vértice

    // segunda serie de búsquedas en profundidad
    for (auto v : order)
        if (!visited[v]) {
            std::vector<int> component;
            dfs(v, adj_rev, component);
            components.push_back(component);
            int root = *component.begin();
            for (auto u : component)
                roots[u] = root;
        }

    // agregar aristas al grafo de condensación
    adj_cond.assign(n, {});
    for (int v = 0; v < n; v++)
        for (auto u : adj[v])
            if (roots[v] != roots[u])
                adj_cond[roots[v]].push_back(roots[u]);
}

La función dfs implementa la búsqueda en profundidad. Recibe como entrada una lista de adyacencia y un vértice de inicio. También recibe una referencia al vector output: cada vértice visitado se agregará a output cuando dfs salga de ese vértice.

Nótese que usamos la función dfs tanto en el primer como en el segundo paso del algoritmo. En el primer paso, pasamos la lista de adyacencia de $G$ y, durante llamadas consecutivas a dfs, seguimos pasando el mismo ‘vector de salida’ order, de modo que al final obtenemos una lista de vértices en orden creciente de tiempos de salida. En el segundo paso, pasamos la lista de adyacencia de $G^T$ y, en cada llamada, pasamos un ‘vector de salida’ vacío component, que nos dará una componente fuertemente conexa a la vez.

Algoritmo de componentes fuertemente conexas de Tarjan

Descripción del algoritmo

El algoritmo descrito fue propuesto por primera vez por Tarjan en 1972. Se basa en realizar una secuencia de llamadas a DFS, usando información inherente a su estructura para determinar las componentes fuertemente conexas (SCC), con un tiempo de ejecución de $O(n+m)$.

Al aplicar el DFS sobre un vértice, recorremos su lista de adyacencia, y si encontramos un vértice que no ha sido visitado, aplicamos el DFS de forma recursiva sobre él.

Consideremos el árbol inducido por la secuencia de llamadas a DFS, al que llamaremos árbol DFS. Una vez que llamamos por primera vez un DFS sobre un vértice de una SCC, todos los vértices de su SCC serán visitados antes de que esta llamada termine, ya que todos son alcanzables entre sí. En el árbol DFS, este primer vértice será un ancestro común de todos los demás vértices de la SCC; definimos este vértice como la raíz de la SCC.

Nótese que las SCC parten de forma perfecta el árbol DFS en subgrafos conexos.

La idea del algoritmo es entonces la siguiente:

• Realizamos una secuencia de llamadas a DFS, aplicándolas de forma recursiva a los vértices de las listas de adyacencia.

• Una vez que terminamos de recorrer la lista de adyacencia de un vértice, de alguna forma podemos determinar si es una raíz o no. Este método se explicará más adelante.

• Si el vértice es una raíz, entonces inmediatamente encontraremos y reclamaremos todos los vértices de su SCC.

Cuando todas las llamadas terminen, se habrán detectado todas las raíces y todos los vértices habrán sido reclamados como parte de alguna SCC.

Analicemos ahora las propiedades del DFS cuando se introduce este proceso de reclamar.

Nótese que, cuando dos vértices pertenecen a la misma componente, su raíz debe ser un ancestro común de ambos vértices.

Ahora debemos encontrar el método que nos permite determinar si un vértice es una raíz o no, y las propiedades del proceso de reclamar son necesarias para su corrección. Para ello, definimos el tiempo de entrada $t_{in}[v]$ para cada vértice $v \in G$, que corresponde a la ‘marca de tiempo’ en la que se llamó al DFS sobre $v$. Por definición, la raíz es el primer vértice de una SCC visitado por el DFS, así que tendrá el valor mínimo de $t_{in}$ de su SCC.

Sea $v$ un vértice y consideremos su subárbol. En el momento en que terminamos de recorrer su lista de adyacencia, cualquier vértice ya visitado por un DFS fuera del subárbol tendrá un valor menor de $t_{in}$, ya que el DFS se llamó primero sobre ellos antes de empezar en $v$.

Al considerar el proceso de reclamar, el valor de $t_{in}$ de todos los vértices no reclamados fuera del subárbol de $v$ es menor que $t_{in}[v]$. Ahora podemos ver cómo usar $t_{in}$ para determinar las raíces. Consideramos el valor mínimo de $t_{in}$ de los vértices no reclamados que podemos alcanzar y propagamos esta información a los ancestros a través de aristas de árbol. Llamaremos al valor propagado $t_{low}$.

Más formalmente, definimos $t_{low}[v]$ como el menor valor de $t_{in}$ que un vértice en el subárbol de $v$ puede alcanzar a través de una arista directa. Por lo tanto, podemos detectar si un vértice $v$ es una raíz o no comprobando si $t_{low}[v] < t_{in}[v]$.

Por último, para reclamar los vértices hay muchas formas de hacerlo, como otro algoritmo de recorrido de grafos, pero también es posible usar una estructura de datos simple para llevar la cuenta de los vértices no reclamados. Para determinar la estructura de datos desde primeros principios, recorramos los métodos que debe implementar, que son solo dos:

• Cuando visitamos un vértice por primera vez, simplemente debemos insertarlo en la estructura de datos, ya que este vértice está no reclamado.

• Cuando encontramos una raíz, debemos encontrar todos los vértices no reclamados restantes en su subárbol y eliminarlos de la estructura de datos.

Podemos encontrar una forma alternativa de describir la operación de eliminación al notar que, inmediatamente después de recorrer la lista de adyacencia de un vértice $v$, todos los vértices colocados en la estructura de datos después de $v$ pertenecen a su subárbol. Si $v$ es una raíz, todos los vértices restantes que se insertaron después de $v$ deben eliminarse. Así, la operación de eliminación se puede describir en cambio como:

• Cuando encontramos una raíz, debemos encontrar y eliminar todos los vértices restantes que se insertaron después de ella.

Ahora podemos ver que esto se puede implementar con una pila:

• Cuando visitamos un vértice por primera vez, lo apilamos.

• Cuando encontramos una raíz, desapilamos todos los elementos hasta desapilar la raíz misma.

Esto por fin nos permite implementar el algoritmo.

La complejidad temporal de la secuencia de llamadas a DFS es $O(n + m)$. Considerando la pila, su complejidad se amortiza a $O(n)$ ya que cada nodo se apila y se desapila solo una vez. La complejidad temporal total es por lo tanto $O(n + m)$.

Como observación adicional, las raíces se encuentran en orden topológico inverso. En el algoritmo, el vértice es una raíz si no hay aristas hacia vértices no reclamados fuera de su subárbol, lo que significa que todas las demás componentes alcanzables están o bien en su subárbol (y por lo tanto sus raíces ya se encontraron) o bien se conectan con vértices ya reclamados fuera del subárbol (cuyas raíces también ya se encontraron). Así, todas las componentes alcanzables ya se encontraron, lo que significa que se introducen en un orden topológico inverso válido del grafo de condensación.

Implementación

vector<int> st;    // - pila que guarda los vértices no reclamados
vector<int> roots; // - registra las raíces de SCC de los vértices
int timer;         // - contador de marcas de tiempo del dfs
vector<int> t_in;  // - registra la marca de tiempo dfs de los vértices
vector<int> t_low; // - registra el menor t_in de vértices no reclamados
                   // alcanzables en el subárbol

// implementa el algoritmo de Tarjan para componentes fuertemente conexas
void dfs(int v, vector<vector<int>> const &adj, vector<vector<int>> &components) {

  t_low[v] = t_in[v] = timer++;
  st.push_back(v);

  for (auto u : adj[v]) {
    if (t_in[u] == -1) { // arista de árbol
      dfs(u, adj, components);
      t_low[v] = min(t_low[v], t_low[u]);
    } else if (roots[u] == -1) { // arista de retroceso, cruzada o hacia adelante a un vértice no reclamado
      t_low[v] = min(t_low[v], t_in[u]);
    }
  }

  if (t_low[v] == t_in[v]) { // el vértice es una raíz
    components.push_back({v}); // inicializa una nueva componente con raíz v
    while (true) {
      int u = st.back();
      st.pop_back();
      roots[u] = v; // reclama el vértice
      if (u == v)
        break;
      components.back().push_back(u); // agrega el vértice u a la componente de v
    }
  }
}

// entrada: adj -- lista de adyacencia de G
// salida: components -- las componentes fuertemente conexas en G
// salida: adj_cond -- lista de adyacencia de G^SCC (por vértices raíz)
void strongly_connected_components(vector<vector<int>> const &adj,
                                   vector<vector<int>> &components,
                                   vector<vector<int>> &adj_cond) {
  components.clear();
  adj_cond.clear();

  int n = adj.size();

  st.clear();
  roots.assign(n, -1);
  timer = 0;
  t_in.assign(n, -1);
  t_low.assign(n, -1);

  // aplica el algoritmo de Tarjan a todos los vértices
  // agrega vértices a las componentes en orden topológico inverso
  for (int v = 0; v < n; v++) {
    if (t_in[v] == -1) {
      dfs(v, adj, components);
    }
  }

  // agrega aristas al grafo de condensación
  adj_cond.assign(n, {});
  for (int v = 0; v < n; v++) {
    for (auto u : adj[v])
      if (roots[v] != roots[u])
        adj_cond[roots[v]].push_back(roots[u]);
  }
}

Tenemos un envío aceptado  con este código en Library Checker.

Como última observación, hay una forma alternativa de iterar por la lista de adyacencia. Actualmente hacemos lo siguiente:

for (auto u : adj[v]) {
  if (t_in[u] == -1) { // arista de árbol
    dfs(u, adj);
    t_low[v] = min(t_low[v], t_low[u]);
  } else if (roots[u] == -1) { // arista de retroceso, cruzada o hacia adelante a un vértice no reclamado
    t_low[v] = min(t_low[v], t_in[u]);
  }
}

De forma alternativa, podríamos hacer:

for (auto u : adj[v]) {
  if (t_in[u] == -1) // el vértice no está visitado
    dfs(u, adj);
  if (roots[u] == -1) // el vértice no ha sido reclamado
    t_low[v] = min(t_low[v], t_low[u]);
}

$t_{low}$ se usa para propagar la información hasta la raíz, y cuando hacemos t_low[v] = min(t_low[v], t_in[u]), sabemos que $u$ y $v$ pertenecen a la misma SCC. Si $t_{low}[u]$ se propaga hasta la raíz de $u$, también se puede propagar a través de $v$ ya que la raíz es la misma. Como $t_{low}[u] \leq t_{in}[u]$, esto no introduce conflictos; solo mejora la cota sobre la raíz de $v$.

Construcción del grafo de condensación

Al construir la lista de adyacencia del grafo de condensación, seleccionamos la raíz de cada componente como el primer vértice de su lista de vértices (esta es una elección arbitraria). Este vértice raíz representa toda su SCC. Para cada vértice v, el valor roots[v] indica el vértice raíz de la SCC a la que pertenece v.

Nuestro grafo de condensación queda dado por los vértices components (una componente fuertemente conexa corresponde a un vértice en el grafo de condensación), y la lista de adyacencia queda dada por adj_cond, usando solo los vértices raíz de las componentes fuertemente conexas. Nótese que generamos una arista de $C$ a $C’$ en $G^\text{SCC}$ por cada arista de algún $a\in C$ a algún $b\in C’$ en $G$ (si $C\neq C’$). Esto implica que, en nuestra implementación, puede haber aristas múltiples entre dos componentes en el grafo de condensación.

Literatura

• Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms [2005].
• M. Sharir. A strong-connectivity algorithm and its applications in data-flow analysis [1979].
• Robert Tarjan. Depth-first search and linear graph algorithms [1972].

Problemas de práctica

• SPOJ - Good Travels 
• SPOJ - Lego 
• Codechef - Chef and Round Run 
• UVA - 11838 - Come and Go 
• UVA 247 - Calling Circles 
• UVA 13057 - Prove Them All 
• UVA 12645 - Water Supply 
• UVA 11770 - Lighting Away 
• UVA 12926 - Trouble in Terrorist Town 
• UVA 11324 - The Largest Clique 
• UVA 11709 - Trust groups 
• UVA 12745 - Wishmaster 
• SPOJ - True Friends 
• SPOJ - Capital City 
• Codeforces - Scheme 
• SPOJ - Ada and Panels 
• CSES - Flight Routes Check 
• CSES - Planets and Kingdoms 
• CSES - Coin Collector 
• Codeforces - Checkposts