Puentes y puntos de articulación

Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Halla las aristas (puentes) y vértices (puntos de articulación) cuya eliminación desconecta el grafo, con tiempos de llegada y low-link.

Complejidad: O(V + E).

Cuándo usarlo

Análisis de conectividad/robustez, componentes biconexas, problemas de ‘qué pasa si quito esta arista/vértice’.

Implementación recomendada (C++)

struct BridgesAP {
    int n, timer = 0;
    vector<vector<pair<int,int>>> g;       // {vecino, id de arista}
    vector<int> tin, low; vector<char> isAP;
    vector<pair<int,int>> bridges;
    BridgesAP(int n) : n(n), g(n), tin(n,-1), low(n), isAP(n,0) {}
    void add(int u, int v, int id) { g[u].push_back({v,id}); g[v].push_back({u,id}); }
    void dfs(int u, int pe) {
        tin[u] = low[u] = timer++; int children = 0;
        for (auto [v, id] : g[u]) {
            if (id == pe) continue;
            if (tin[v] != -1) low[u] = min(low[u], tin[v]);
            else {
                dfs(v, id); low[u] = min(low[u], low[v]);
                if (low[v] > tin[u]) bridges.push_back({u, v});
                if (low[v] >= tin[u] && pe != -1) isAP[u] = 1;
                children++;
            }
        }
        if (pe == -1 && children > 1) isAP[u] = 1;
    }
    void run() { for (int i = 0; i < n; i++) if (tin[i] == -1) dfs(i, -1); }
};

⚠️ Notas

Intuición del low: low[v] es lo más arriba que alcanza el subárbol de v usando una arista hacia atrás; si no logra subir más allá de u, cortar u-v desconecta. Se pasa el id de la arista (no el padre) para manejar bien aristas múltiples. Un puente cumple low[v] > tin[u]; articulación, low[v] >= tin[u]. ⚠️ La recursión aquí es de profundidad O(n) (un árbol en forma de camino la lleva al máximo). En la IOI eso no es problema: el run_cpp.sh oficial sube la pila al mismo valor que la memoria (2 GB en 2023). En tu propia máquina sí lo es: el límite por defecto son 8 MB y revienta cerca de n = 120.000. Si se cae localmente pero pasa en el juez, es esto — corre ulimit -s unlimited (o ulimit -s 65520 en macOS) antes de probar.