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.