Ciclos, ordem topológica e conetividade

Uma DFS regista a descoberta e o fim de cada chamada. Uma aresta para uma chamada ainda ativa fecha um ciclo dirigido. Uma aresta para uma chamada terminada pode apenas ligar dois ramos. Para distinguir os casos, guardamos mais informação do que um conjunto de visitados.

Assume as representações e a marcação na descoberta da página anterior. A novidade são os tempos e valores low que identificam ciclos, ordem e pontos críticos.

Ciclos dirigidos e não dirigidos

Numa DFS dirigida, usa três estados: branco, ainda não descoberto; cinzento, chamada ainda ativa; preto, chamada terminada. Uma aresta para um vértice cinzento fecha um ciclo, porque o destino é um antepassado no caminho de chamadas, que já tem um caminho até ao vértice atual. Uma aresta para preto não prova um ciclo, porque pode ligar a um ramo que já terminou.

Para reconstruíres um ciclo, segue os pais do vértice atual até ao antepassado cinzento e fecha com a aresta encontrada. Um laço é um ciclo de comprimento um, se a definição do problema o permitir. Repete DFS em todos os vértices para detetares ciclos em componentes desligadas da primeira origem.

Num grafo não dirigido, a aresta de regresso ao pai existe na lista e não é, por si só, um ciclo. Ignora apenas essa aresta. Se houver arestas paralelas, ignorar todos os vizinhos iguais ao pai perde o ciclo de duas arestas: atribui um identificador a cada aresta e ignora só o identificador usado para entrar no vértice.

Ordem topológica

Uma ordem topológica é uma sequência de todos os vértices tal que, para cada aresta u->v, u aparece antes de v. Existe exatamente quando o grafo dirigido é acíclico, um DAG.

Na DFS de um DAG, uma aresta u->v não pode apontar para cinzento. As arestas para branco são de árvore; as que chegam a cinzento são de trás. Para preto, distingue avanço, se o destino é descendente, de cruzamento, se não é. A cor preta sozinha não separa estes dois casos. Se aponta para branco, a chamada de v termina antes de u; se aponta para preto, v já terminou. Logo ordenar por tempos de saída decrescentes coloca u antes de v. Deteta ciclos antes de apresentares a sequência como uma ordem válida.

O algoritmo de Kahn guarda os graus de entrada e uma fila dos vértices de grau de entrada zero. Retira um deles, acrescenta-o à ordem e reduz o grau de entrada dos seus destinos, colocando os que chegam a zero na fila. O invariante diz que o grau restante conta arestas vindas de vértices ainda não retirados. Um vértice de grau de entrada zero não tem predecessor restante e pode ser escolhido com segurança.

Para as arestas 0->2, 1->2, 2->3, 1->4, começa com a fila [0,1]. Retirar 0 deixa o grau de 2 igual a 1. Retirar 1 liberta 2 e 4. A ordem com esta fila é [0,1,2,4,3]. [1,0,4,2,3] também é válida. Se acrescentares 3->1, sobram vértices sem grau de entrada zero: existe um ciclo. Kahn devolve uma ordem completa se e só se retirar V vértices.

Ambas as abordagens custam $O(V+E)$ e espaço auxiliar $O(V)$. Para escolheres sempre o menor vértice disponível, substitui a fila por uma fila de prioridade, como a heap de um capítulo posterior; a escolha acrescenta um fator logarítmico nas operações de prioridade.

Unicidade da ordem topológica

Kahn também permite verificar se a ordem é única. Num DAG, se em cada passo há exatamente um vértice de grau de entrada zero, todas as escolhas estão forçadas. Se num passo houver dois, podes escolher qualquer um primeiro e continuar; obténs pelo menos duas ordens. Não há um caminho do primeiro disponível para o segundo, pois isso daria ao segundo um predecessor ainda presente.

A cadeia A->B->C->D tem uma única ordem A,B,C,D. Acrescentar A->C não muda a unicidade. Já A->C,B->C permite começar por A ou B, mesmo sendo fracamente conexo. Ter uma única componente fraca não força a ordem.

Componentes fortes e fracas

Em grafos não dirigidos, uma componente conexa é um conjunto máximo de vértices ligados por caminhos. Num grafo dirigido, uma componente fortemente conexa, SCC, é um conjunto máximo em que cada par é alcançável nos dois sentidos. A componente fraca ignora os sentidos das arestas e pode juntar várias SCC.

Contrair cada SCC a um vértice produz um DAG: desenha cada SCC como um nó e conserva uma aresta entre SCC distintas; um ciclo entre componentes permitiria alcançar todas nos dois sentidos e obrigaria a juntá-las numa só. Vértices isolados são componentes individuais.

Para construir um grafo com um número pedido de SCCs, desenha primeiro cada componente com caminhos internos nos dois sentidos, depois liga-as num DAG. Por exemplo, ciclos 0->1->0 e 2->3->2, mais o vértice 4, unidos por 1->2 e 3->4, dão exatamente três SCCs e uma componente fraca. Uma aresta de regresso que feche um ciclo entre as componentes pode uni-las.

No exemplo do programa abaixo, 0 e 1 alcançam-se mutuamente, tal como 2 e 3. A aresta 1->2 liga componentes, mas não há caminho de regresso. É essa diferença que o desenho conserva depois da contração.

Tarjan e a pilha de componentes

Tarjan faz uma DFS, guarda disc[u], o tempo de descoberta, e low[u], o menor tempo alcançável a partir de u sem sair da região ainda por atribuir a uma componente. Mantém uma pilha de vértices descobertos mas ainda não atribuídos a uma SCC.

Ao entrar em u, define disc[u]=low[u] e empilha-o. Para cada aresta u->v, decide pelo estado de v:

1. Se v ainda não foi descoberto, visita-o primeiro e depois propaga: low[u]=min(low[u],low[v]). O filho já resume o que a sua subárvore alcança.
2. Se v já foi descoberto e continua na pilha de componentes, usa o tempo de descoberta: low[u]=min(low[u],disc[v]). Usa disc[v], não o low[v] já calculado, que resume a exploração de outro ramo.
3. Se v já pertence a uma componente terminada, ignora essa aresta: nada do que v alcança volta a u por dentro da mesma componente.

Quando low[u]==disc[u], u é a raiz de uma componente: retira da pilha até incluir u, atribuindo a mesma componente a todos. Os vértices retirados conseguem alcançar essa raiz pela informação acumulada; a raiz alcança-os pelos caminhos de descoberta. A condição impede que a componente fique ligada a um antepassado ainda pendente.

Considera as arestas 0->1, 1->0, 0->2 e 2->1. Começa a DFS em 0 e visita 1 antes de 2:

1. Descobrimos 0 e 1, com disc[0]=0 e disc[1]=1. A aresta 1->0 faz low[1]=0. A chamada de 1 termina, mas 1 fica na pilha de componentes porque low[1]!=disc[1]. Neste momento, 1 é preto, não cinzento.
2. Descobrimos 2, com disc[2]=low[2]=2. Ao examinar 2->1, sabemos que 1 ainda está na pilha de componentes. Fazemos low[2]=min(2,disc[1])=1. Por isso, 2 também fica na pilha quando a sua chamada termina.
3. No fim da chamada de 0, low[0]=disc[0]=0. Retiramos 2, 1 e 0, obtendo uma única SCC, {0,1,2}.

Se verificasses apenas «cinzento» no segundo passo, ignorarias 2->1 e retirarias 2 como uma componente isolada. Isso seria errado: 0 chega a 2 diretamente e 2 regressa a 0 por 2->1->0. A pilha de componentes conserva precisamente a ligação que a pilha de chamadas já não mostra.

#include <algorithm>
#include <iostream>
#include <vector>
class Componentes {
    const std::vector<std::vector<int>>& g;
    std::vector<int> descoberta, low, pilha, componente;
    std::vector<bool> naPilha;
    int tempo = 0, total = 0;
    void dfs(int u) {
        descoberta[u] = low[u] = tempo++;
        pilha.push_back(u); naPilha[u] = true;
        for (int v : g[u]) {
            if (descoberta[v] == -1) { dfs(v); low[u] = std::min(low[u], low[v]); }
            else if (naPilha[v]) low[u] = std::min(low[u], descoberta[v]);
        }
        if (low[u] != descoberta[u]) return;
        while (true) {
            const int v = pilha.back(); pilha.pop_back();
            naPilha[v] = false; componente[v] = total;
            if (v == u) break;
        }
        ++total;
    }
public:
    explicit Componentes(const std::vector<std::vector<int>>& grafo)
        : g(grafo), descoberta(g.size(), -1), low(g.size()),
          componente(g.size(), -1), naPilha(g.size(), false) {
        for (std::size_t u = 0; u < g.size(); ++u)
            if (descoberta[u] == -1) dfs(static_cast<int>(u));
    }
    int quantidade() const { return total; }
    bool juntos(int u, int v) const { return componente[u] == componente[v]; }
};
int main() {
    const std::vector<std::vector<int>> g{{1},{0,2},{3},{2,4},{}};
    Componentes c(g);
    std::cout << "componentes: " << c.quantidade() << '\n';
    std::cout << "0 e 1: " << c.juntos(0,1) << '\n';
    std::cout << "2 e 3: " << c.juntos(2,3) << '\n';
    std::cout << "0 e 4: " << c.juntos(0,4) << '\n';
}

As componentes são {0,1}, {2,3} e {4}. A DFS descobre os vértices por esta ordem: 0,1,2,3,4. A aresta 1->0 reduz low[1] para 0; 3->2 reduz low[3] para 2. O vértice 4 fecha primeiro, depois 2 fecha com 3 e por fim 0 fecha com 1. Os números usados para identificar componentes dependem da ordem de visita e não são parte da definição.

Cada vértice entra e sai da pilha uma vez e cada aresta é examinada uma vez. Tempo $O(V+E)$ e espaço auxiliar $O(V)$. O programa pressupõe destinos válidos e trata também vértices isolados e um grafo vazio.

Pontes e pontos de articulação

Agora o grafo é não dirigido. Uma ponte é uma aresta cuja remoção aumenta o número de componentes. Um ponto de articulação é um vértice cuja remoção, com as suas arestas, aumenta esse número. A definição também funciona em grafos já desconexos.

Na DFS, inicializa low[u]=disc[u]. Uma aresta de árvore u-v contribui com low[v] depois de visitar v; uma aresta para um vértice já descoberto, diferente da aresta de entrada, contribui com disc[v]. Aqui low[v] indica o antepassado mais antigo alcançável pela subárvore de v usando arestas de árvore e uma aresta de retorno.

Para um filho DFS v de u:

• u-v é ponte se low[v]>disc[u]. A subárvore não consegue voltar a u nem a um antepassado sem essa aresta.
• Um u que não é raiz é articulação se algum filho satisfaz low[v]>=disc[u]. Sem u, esse ramo não alcança a zona anterior da DFS.
• A raiz é articulação se tem pelo menos dois filhos na árvore DFS. O seu grau no grafo não é o critério.

A desigualdade das pontes é estrita. Com low[v]==disc[u], existe uma ligação de retorno a u e a aresta não é ponte; retirar o próprio u ainda pode separar o ramo, justificando a igualdade para articulação.

No triângulo 0-1-2-0, acrescenta 1-3 e 3-4, e um vértice isolado 5. Com DFS a partir de 0 por ordem crescente e contador incrementado a cada descoberta, disc=[0,1,2,3,4,5] e low=[0,0,0,3,4,5]; os retornos do triângulo baixam low[2] e low[1] para 0. Como low[4]=4>disc[3]=3, a aresta 3-4 é ponte, e como low[3]=3>disc[1]=1, 1-3 também é; as desigualdades alargadas low[4]>=disc[3] e low[3]>=disc[1] marcam 3 e 1 como articulações. A raiz 0 tem um só filho DFS e não é articulação, e as arestas do triângulo têm caminhos alternativos, por isso não são pontes. Uma aresta paralela entre 3 e 4 faria essa ligação deixar de ser ponte.

Mantém identificadores de arestas para suportares paralelas e recomeça DFS em cada vértice ainda não descoberto. Tempo $O(V+E)$, espaço auxiliar $O(V)$. Para verificares uma implementação em grafos pequenos, remove cada aresta ou vértice, conta componentes de novo e compara com as condições low; essa referência lenta testa a definição diretamente.