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.
Escolha um vértice arbitrário(raiz) do grafo e execute uma DFS a partir dele. Observe que:
Digamos que estamos na DFS, examinando as arestas a partir do vértice $v\ne root$. Se a aresta atual $(v, to)$ for tal que nenhum dos vértices $to$ ou seus descendentes na árvore da travessia da DFS tiver uma back-edge(aresta de volta) para qualquer ancestral de $v$, então $v$ será uma articulação ponto. Caso contrário, $v$ não é um ponto de articulação.
Vamos considerar o caso em que $v=raiz$. Esse vértice será o ponto de articulação se, e somente se, esse vértice tiver mais de um filho na árvore da DFS.
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]$.
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).