Puntos de Articulación y Puentes

¿Qué son?

• Punto de articulación: Un nodo cuya eliminación desconecta el grafo.
• Puente: Una arista cuya eliminación desconecta el grafo.

Analogía: En una red eléctrica, un punto de articulación es una subestación cuya falla deja sin luz a parte de la ciudad. Un puente es un cable único cuya rotura desconecta zonas.

Algoritmo de Tarjan

Usa DFS con dos arreglos:

• tin[u]: tiempo de descubrimiento de u.
• low[u]: menor tin alcanzable desde el subárbol de u usando aristas de retroceso.

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

const int MAXN = 100005;
vector<int> adj[MAXN];
int tin[MAXN], low[MAXN], timer_val = 0;
bool vis[MAXN];
set<int> articulaciones;
vector<pair<int,int>> puentes;

void dfs(int u, int padre) {
    vis[u] = true;
    tin[u] = low[u] = timer_val++;
    int hijos = 0;

    for (int v : adj[u]) {
        if (v == padre) continue;

        if (vis[v]) {
            low[u] = min(low[u], tin[v]);
        } else {
            hijos++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            // Punto de articulación
            if (padre == -1 && hijos > 1) {
                articulaciones.insert(u);
            }
            if (padre != -1 && low[v] >= tin[u]) {
                articulaciones.insert(u);
            }

            // Puente
            if (low[v] > tin[u]) {
                puentes.push_back({u, v});
            }
        }
    }
}

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);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs(i, -1);
    }

    cout << "Puntos de articulación: ";
    for (int v : articulaciones) cout << v << " ";
    cout << endl;

    cout << "Puentes: ";
    for (auto [u, v] : puentes) cout << "(" << u << "," << v << ") ";
    cout << endl;

    return 0;
}

Complejidad: $O(V + E)$

Condiciones

Puente (u, v): low[v] > tin[u] — el subárbol de v no puede "regresar" más arriba de u.

Punto de articulación u:

• Si u es la raíz del DFS: tiene más de un hijo en el árbol DFS.
• Si no es la raíz: existe un hijo v donde low[v] >= tin[u].

Ejercicio de práctica

Dado un grafo no dirigido, encuentra todos los puentes.

Ver solución

Usa el algoritmo de Tarjan. Los puentes son las aristas donde low[v] > tin[u].