Componentes Fuertemente Conexas (SCC)

¿Qué es una SCC?

En un grafo dirigido, una Componente Fuertemente Conexa (Strongly Connected Component) es un grupo máximo de nodos donde puedes llegar de cualquiera a cualquier otro siguiendo la dirección de las aristas.

Analogía: En una ciudad con calles de un solo sentido, una SCC es una zona donde puedes ir de cualquier esquina a cualquier otra (quizás dando vueltas).

Algoritmo de Kosaraju

Dos pasadas de DFS:

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN], radj[MAXN];  // Grafo y grafo transpuesto
bool vis[MAXN];
int comp[MAXN];
stack<int> orden;

void dfs1(int u) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (!vis[v]) dfs1(v);
    }
    orden.push(u);  // Postorden
}

void dfs2(int u, int id) {
    vis[u] = true;
    comp[u] = id;
    for (int v : radj[u]) {
        if (!vis[v]) dfs2(v, id);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        radj[v].push_back(u);  // Grafo transpuesto
    }

    // Paso 1: DFS en el grafo original
    fill(vis, vis + n + 1, false);
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs1(i);
    }

    // Paso 2: DFS en el grafo transpuesto, en orden inverso de finalización
    fill(vis, vis + n + 1, false);
    int numSCC = 0;
    while (!orden.empty()) {
        int u = orden.top(); orden.pop();
        if (!vis[u]) {
            numSCC++;
            dfs2(u, numSCC);
        }
    }

    cout << "SCCs: " << numSCC << endl;
    for (int i = 1; i <= n; i++) {
        cout << "Nodo " << i << " → SCC " << comp[i] << endl;
    }

    return 0;
}

Complejidad: $O(V + E)$

¿Por qué funciona?

1. El primer DFS ordena los nodos por tiempo de finalización.
2. Procesar en orden inverso en el grafo transpuesto asegura que cada DFS solo alcanza nodos de la misma SCC.

Grafo de condensación (DAG de SCCs)

Después de encontrar las SCCs, puedes "contraer" cada SCC en un solo nodo, creando un DAG:

// Después de Kosaraju
set<pair<int,int>> aristasDAG;

for (int u = 1; u <= n; u++) {
    for (int v : adj[u]) {
        if (comp[u] != comp[v]) {
            aristasDAG.insert({comp[u], comp[v]});
        }
    }
}

Este DAG es útil para aplicar ordenamiento topológico, DP en grafos, etc.

Ejercicio de práctica

Dado un grafo dirigido, encuentra el número de SCCs.

Ver solución

Usa el algoritmo de Kosaraju mostrado arriba. La respuesta es numSCC.