Localizando pontos de articulação em um grafo em $O(N+M)$

Nos é dado um grafo não direcionado. Um ponto de articulação (ou vértice de corte) é definido como um vértice que, quando removido junto com as arestas associadas, desconecta o grafo (ou mais precisamente, aumenta o número de componentes conectados no grafo). A tarefa é encontrar todos os pontos de articulação no grafo fornecido.

O algoritmo descrito aqui é baseado em uma DFS e tem complexidade $O(N+M)$, onde $N$ é o número de vértices e $M$ é o número de arestas no grafo.

Algoritmo

Escolha um vértice arbitrário(raiz) do grafo e execute uma DFS a partir dele. Observe que:

Agora temos que aprender a verificar esse fato para cada vértice com eficiência. Usaremos o "tempo de entrada" do nó calculado pela DFS.

Então, deixe que $tin[v]$ denotar o tempo de entrada para o nó $v$. Introduzimos uma array $low[v]$ que permitirá verificar o fato para cada vértice $v$. $low[v]$ é o mínimo de $tin[v]$, os tempos de entrada $tin[p]$ para cada nó $p$ que é conectado ao nó $v$ por uma back-edge $(v, p)$ e os valores $low[to]$ para cada vértice $to$ que é um descendente direto de $v$ na árvore da DFS:

$$low[v] = \min \begin{cases} tin[v] \\ tin[p] &\text{ para todo }p\text{ em que }(v, p)\text{ back edge} \\ low[to]& \text{ para todo }to\text{ em que }(v, to)\text{ tree edge} \end{cases}$$

Agora, há uma back edge do vértice $v$ ou de um de seus descendentes para um de seus ancestrais se, e somente se, o vértice $v$ tiver um filho $to$ no qual $low[to] < tin[v]$. Se $low[to] = tin[v]$, a back edge vai diretamente para $v$, caso contrário, ela vai para um dos ancestrais de $v$.

Portanto, o vértice $v$ na árvore da DFS é um ponto de articulação(vértice de corte) se, e somente se, $low[to] \geq tin[v]$.

Implementação

A implementação precisa distinguir três casos: quando percorremos a aresta na árvore da DFS, quando encontramos uma back edge de um ancestral do vértice e quando retornamos a um parente do vértice. Estes são os casos:

Para implementar isso, precisamos de uma função DFS que aceite o vértice parente do nó atual.

Implementação em C++

int n; // número de nós
vector<vector<int>> adj; // lista de adjacência - grafo

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);
    }
}

A função principal é find_cutpoints; ela executa a inicialização necessária e inicia a DFS em cada componente conectado do grafo.

A função IS_CUTPOINT(a) processa o fato de que o vértice $a$ é um ponto de articulação, por exemplo, printando ele (isso pode ser chamado várias vezes para um vértice).

Problemas