Encontrar puntos de articulación en un grafo en $O(N+M)$

Se nos da un grafo no dirigido. Un punto de articulación (o cut vertex) se define como un vértice que, al quitarlo junto con las aristas asociadas, desconecta el grafo (o, más precisamente, aumenta el número de componentes conexas del grafo). La tarea es encontrar todos los puntos de articulación del grafo dado.

El algoritmo descrito acá se basa en búsqueda en profundidad y tiene complejidad $O(N+M)$, donde $N$ es la cantidad de vértices y $M$ la cantidad de aristas del grafo.

Algoritmo

Elegí un vértice arbitrario del grafo $root$ y corré búsqueda en profundidad desde él. Nótese el siguiente hecho (fácil de demostrar):

• Digamos que estamos en el DFS, mirando las aristas que salen del vértice $v\ne root$. Si la arista actual $(v, to)$ es tal que ninguno de los vértices $to$ o de sus descendientes en el árbol de recorrido DFS tiene una back-edge hacia alguno de los ancestros de $v$, entonces $v$ es un punto de articulación. En caso contrario, $v$ no es un punto de articulación.

• Consideremos el caso restante $v=root$. Este vértice será punto de articulación si y solo si tiene más de un hijo en el árbol DFS.

Ahora hay que aprender a chequear este hecho para cada vértice de forma eficiente. Usaremos el “tiempo de entrada al nodo” computado por la búsqueda en profundidad.

Así, sea $tin[v]$ el tiempo de entrada del nodo $v$. Introducimos un arreglo $low[v]$ que nos permitirá chequear el hecho para cada vértice $v$. $low[v]$ es el mínimo de $tin[v]$, los tiempos de entrada $tin[p]$ de cada nodo $p$ conectado al nodo $v$ vía una back-edge $(v, p)$ y los valores de $low[to]$ de cada vértice $to$ que es descendiente directo de $v$ en el árbol DFS:

$$low[v] = \min$$$$\begin{cases} tin[v] \ tin[p] &\text{ for all }p\text{ for which }(v, p)\text{ is a back edge} \ low[to]& \text{ for all }to\text{ for which }(v, to)\text{ is a tree edge} \end{cases}$$

Ahora, hay una back-edge desde el vértice $v$ o uno de sus descendientes hacia uno de sus ancestros si y solo si el vértice $v$ tiene un hijo $to$ para el cual $low[to] < tin[v]$. Si $low[to] = tin[v]$, la back-edge llega directamente a $v$; si no, llega a uno de los ancestros de $v$.

Así, el vértice $v$ en el árbol DFS es un punto de articulación si y solo si $low[to] \geq tin[v]$.

Implementación

La implementación necesita distinguir tres casos: cuando bajamos por la arista en el árbol DFS, cuando encontramos una back-edge hacia un ancestro del vértice y cuando volvemos al padre del vértice. Estos son los casos:

• $visited[to] = false$ - la arista es parte del árbol DFS;
• $visited[to] = true$ && $to \neq parent$ - la arista es una back-edge hacia uno de los ancestros;
• $to = parent$ - la arista vuelve al padre en el árbol DFS.

Para implementar esto, necesitamos una función de búsqueda en profundidad que acepte el vértice padre del nodo actual.

int n; // number of nodes
vector<vector<int>> adj; // adjacency list of graph
 
vector<bool> visited;
vector<int> tin, low;
int timer;
 
void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    int children=0;
    for (int to : adj[v]) {
        if (to == p) continue;
        if (visited[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] >= tin[v] && p!=-1)
                IS_CUTPOINT(v);
            ++children;
        }
    }
    if(p == -1 && children > 1)
        IS_CUTPOINT(v);
}
 
void find_cutpoints() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs (i);
    }
}

La función principal es find_cutpoints; hace la inicialización necesaria y arranca búsqueda en profundidad en cada componente conexa del grafo.

La función IS_CUTPOINT(a) es alguna función que procesará el hecho de que el vértice $a$ es un punto de articulación, por ejemplo, imprimirlo (cuidado: se puede llamar varias veces para un mismo vértice).

Problemas de práctica

• UVA #10199 “Tourist Guide”  [difficulty: low]
• UVA #315 “Network”  [difficulty: low]
• SPOJ - Submerging Islands 
• Codeforces - Cutting Figure