Componentes Fuertemente Conexas (SCC)

En la teoría de grafos dirigidos, un grafo se considera fuertemente conexo si existe al menos un camino dirigido entre cualquier par de vértices. Una componente fuertemente conexa (SCC) se define como un subgrafo maximal que cumple con esta propiedad de alcanzabilidad bidireccional.

Clasificación de Aristas en el Árbol DFS

Al ejecutar un recorrido en profundidad (DFS) sobre un grafo dirigido, las aristas se categorizan en cuatro tipos fundamentales según su relación con el árbol de expansión generado:

• Aristas de árbol: Conectan un vértice procesado con uno no descubierto, estructurando el recorrido principal.
• Aristas de retroceso: Enlazan un nodo con uno de sus ancestros directos en el árbol DFS, indicando la presencia de ciclos.
• Aristas cruzadas: Conectan un nodo con otro ya visitado que no pertenece a su línea de ascendencia ni descendencia.
• Aristas hacia adelante: Van desde un nodo hacia un descendiente que no es un hijo inmediato en el árbol.

Algoritmo de Tarjan para SCC

El enfoque de Tarjan identifica las SCC en un solo recorrido DFS. Se fundamenta en que los nodos de una misma SCC conforman un subárbol dentro del árbol DFS. Para operacionalizar esto, se monitorean dos métricas para cada vértice u:

1. discovery_time[u]: El timestamp exacto en el que el nodo es visitado por primera vez.
2. lowest_reachable[u]: El discovery_time más antiguo alcanzable desde el subárbol de u utilizando como máximo una arista de retroceso.

Durante la exploración, la métrica lowest_reachable se propaga bajo las siguientes reglas:

• Si un vecino v no ha sido visitado, se explora recursivamente y se hereda su valor mínimo.
• Si v fue visitado y aún reside en la pila de recursión, se actualiza el límite inferior usando el tiempo de descubrimiento de v.
• Si v ya fue extraído de la pila, pertenece a una SCC previamente consolidada y se omite.

Cuando se cumple que discovery_time[u] == lowest_reachable[u], se ha localizado la raíz de una SCC. Todos los nodos acumulados en la pila desde u hacia arriba conforman dicha componente.

#include <vector>
#include <algorithm>

std::vector<std::vector<int>> adjacency_list;
std::vector<int> discovery_time, lowest_reachable, stack_nodes, scc_assignment;
std::vector<bool> in_stack;
int timer = 0, scc_count = 0;

void compute_scc(int current_node) {
    discovery_time[current_node] = lowest_reachable[current_node] = ++timer;
    stack_nodes.push_back(current_node);
    in_stack[current_node] = true;

    for (int neighbor : adjacency_list[current_node]) {
        if (!discovery_time[neighbor]) {
            compute_scc(neighbor);
            lowest_reachable[current_node] = std::min(lowest_reachable[current_node], lowest_reachable[neighbor]);
        } else if (in_stack[neighbor]) {
            lowest_reachable[current_node] = std::min(lowest_reachable[current_node], discovery_time[neighbor]);
        }
    }

    if (lowest_reachable[current_node] == discovery_time[current_node]) {
        ++scc_count;
        int extracted_node;
        do {
            extracted_node = stack_nodes.back();
            stack_nodes.pop_back();
            in_stack[extracted_node] = false;
            scc_assignment[extracted_node] = scc_count;
        } while (extracted_node != current_node);
    }
}

Componentes Biconexas en Grafos No Dirigidos

El análisis de biconexión se aplica exclusivamente a grafos no dirigidos y se ramifica en dos conceptos distintos: bicnoexión por aristas y biconexión por vértices.

Componentes Biconexas por Aristas (EBCC)

Un grafo es biconexo por aristas si la supresión de cualquier arista individual no fragmenta su conectividad. Una EBCC es el subgrafo maximal que preserva esta característica. A diferencia de la biconexión por vértices, esta propiedad es transitiva.

Detección de Puentes

Un puente (o arista de corte) es aquella cuya eliminación incrementa el número de componentes conexas del grafo. En el contexto del árbol DFS, una arista que conecta a un padre u con su hijo v se clasifica como puente si lowest_reachable[v] > discovery_time[u]. Esta desigualdad revela que el subárbol de v carece de aristas de retroceso hacia u o sus ancestros. Para manejar grafos con aristas múltiples de manera robusta, se recomienda asignar identificadores únicos a las aristas en lugar de rastrear simplemente el nodo padre.

struct Edge {
    int target, id;
};

std::vector<std::vector<Edge>> undirected_graph;
std::vector<int> disc, low, component_stack, ebcc_id;
std::vector<bool> is_in_stack;
int time_counter = 0, ebcc_total = 0;

void compute_ebcc(int u, int parent_edge_id) {
    disc[u] = low[u] = ++time_counter;
    component_stack.push_back(u);
    is_in_stack[u] = true;

    for (const auto& edge : undirected_graph[u]) {
        int v = edge.target;
        if (edge.id == parent_edge_id) continue; 

        if (!disc[v]) {
            compute_ebcc(v, edge.id);
            low[u] = std::min(low[u], low[v]);
        } else if (is_in_stack[v]) {
            low[u] = std::min(low[u], disc[v]);
        }
    }

    if (low[u] == disc[u]) {
        ++ebcc_total;
        int node;
        do {
            node = component_stack.back();
            component_stack.pop_back();
            is_in_stack[node] = false;
            ebcc_id[node] = ebcc_total;
        } while (node != u);
    }
}

Componentes Biconexas por Vértices (VBCC)

Un grafo se considera biconexo por vértices si la remoción de cualquier vértice único no lo desconecta. La VBCC es el subgrafo maximal que cumple esto. Es crucial notar que esta relación no es transitiva. Dos VBCC diferentes pueden intersectarse en exactamente un vértice, el cual actúa como un punto de articulación.

Identificación de Puntos de Articulación

Un punto de articulación es un vértice crítico cuya eliminación divide el grafo. Las reglas de detección varían según la posición del nodo en el árbol DFS:

• Nodo raíz: Actúa como punto de articulación únicamente si posee dos o más subárboles hijos independientes.
• Nodo interno u: Es un punto de articulación si existe algún hijo v donde lowest_reachable[v] >= discovery_time[u]. Esto implica que el subárbol de v depende exclusivamente de u para comunicarse con el resto del grafo.

Para segmentar las VBCC, se emplea una pila auxiliar. Al detectarse un punto de articulación mediante la condición anterior, se extraen los nodos de la pila hasta alcanzar al hijo v, agrupándolos junto con u para formar una componente.

std::vector<std::vector<int>> graph;
std::vector<int> dfn, low_link, stk;
std::vector<bool> is_cut_vertex;
std::vector<std::vector<int>> vbcc_list;
int dfs_timer = 0;

void extract_vbcc(int u, int parent) {
    dfn[u] = low_link[u] = ++dfs_timer;
    stk.push_back(u);
    int children_count = 0;

    for (int v : graph[u]) {
        if (v == parent) continue;

        if (!dfn[v]) {
            children_count++;
            extract_vbcc(v, u);
            low_link[u] = std::min(low_link[u], low_link[v]);

            if (low_link[v] >= dfn[u]) {
                if (parent != 0) is_cut_vertex[u] = true;
                
                std::vector<int> current_vbcc;
                int popped_node;
                do {
                    popped_node = stk.back();
                    stk.pop_back();
                    current_vbcc.push_back(popped_node);
                } while (popped_node != v);
                current_vbcc.push_back(u);
                vbcc_list.push_back(current_vbcc);
            }
        } else {
            low_link[u] = std::min(low_link[u], dfn[v]);
        }
    }

    if (parent == 0 && children_count >= 2) {
        is_cut_vertex[u] = true;
    }
    if (parent == 0 && children_count == 0) {
        vbcc_list.push_back({u});
    }
}

Condensación de Grafos

La condensación es una técnica de abstracción donde todos los vértices pertenecientes a una misma componente conexa (SCC, EBCC o VBCC) se fusionan en un único supernodo. Las aristas que conectan nodos dentro de la misma componente se descartan, mientras que las aristas entre componentes distintas se redirigen hacia sus respectivos supernodos. Aplicado a componentes fuertemente conexas, este proceso garantiza la transformación del grafo original en un Grafo Dirigido Acíclico (DAG).

struct DirectedEdge {
    int source, destination;
};

std::vector<DirectedEdge> original_edges;
std::vector<std::vector<int>> condensed_dag;
std::vector<int> in_degree;

void build_condensed_dag(int total_edges, int total_sccs) {
    condensed_dag.resize(total_sccs + 1);
    in_degree.assign(total_sccs + 1, 0);

    for (int i = 0; i < total_edges; ++i) {
        int u_component = scc_assignment[original_edges[i].source];
        int v_component = scc_assignment[original_edges[i].destination];
        
        if (u_component != v_component) {
            condensed_dag[u_component].push_back(v_component);
            in_degree[v_component]++;
        }
    }
}