Fundamentos: Vazamento e Ordenação

Para compreender algoritmos de decomposição em grafos, é essencial definir dois vetores principais durante uma travessia por profundidade (DFS): o vetor dfsOrder (ou discovery time) e o vetor minReach (frequentemente chamado de low link).

• dfsOrder: Representa o momento temporal exato em que um vértice é visitado pela primeira vez na árvore de DFS.
• minReach: Armazena o menor valor de dfsOrder alcançável a partir daquele nó através de uma arista de retorno (back-edge) dentro da árvore de DFS.

Um elemento da pilha de travessia é fundamental para rastrear os componentes atuais sendo explorados. Ao iniciar a recursão no vértice atual u, inicializamos seus tempos de visita e baixa visita. A lógica difere dependendo se o nó adjacente v já foi processado ou se está ativo na pilha.

Algoritmo de Condensação de Componentes Fortemente Conexos

O objetivo deste método é identificar grupos de vértices onde cada par de nós possui um caminho cíclico entre si. Durante o processo recursivo:

1. Se o vizinho v ainda não foi visitado, eniciamos a busca recursiva nele. Após o retorno, atualizamos minReach[u] com o mínimo entre seu valor atual e minReach[v].
2. Se v já foi visitado e permanece empilhado na estrutura de dados, significa que ele é um ancestor ou parte de um ciclo. Portanto, atualizamos minReach[u] com o dfsOrder[v].

Quando a condição minReach[u] == dfsOrder[u] ocorre, identificamos a raiz de um novo componente forte. Todos os nós acima dele na pilha pertencem ao mesmo grupo e devem ser removidos e rotulados.

void encontrarSCC(int u) {
    dfn[u] = minRach[u] = ++tempoGlobal;
    empilhar.push(u);
    marcada[u] = true;

    for (int i = primeiroNo[u]; i != 0; i = proximaAresta[i]) {
        int vizinho = arr[vezinhos].destino;
        
        if (!dfn[vizinho]) {
            encontrarSCC(vizinho);
            minRach[u] = std::min(minRach[u], minRach[vizinho]);
        } else if (marcada[vizinho]) {
            minRach[u] = std::min(minRach[u], dfn[vizinho]);
        }
    }

    if (minRach[u] == dfn[u]) {
        int topo = empilhar.top();
        empilhar.pop();
        marcado[topo] = false;
        
        compID[topo] = contadorSCC;
        while (topo != u) {
            topo = empilhar.top();
            empilhar.pop();
            marcado[topo] = false;
            compID[topo] = contadorSCC++;
        }
    }
}

Pontos de Corte e Pontes em Grafos Não-Direcionados

No contexto de grafos não-direcionados, definimos novos critérios. O conceito de minReach muda ligeiramente para indicar o menor número de visita alcançável sem passar pelo pai direto da árvore de DFS.

A condição clássica para um nó u (não raiz) ser um ponto de corte é minReach[v] >= dfn[u] para algum filho v. Isso implica que remover u desconecta v das partes anteriores da árvore. Para a raiz da DFS, ela é ponto de corte apenas se possuir mais de um filho imediato.

// Identificação de pontos de corte e pontes
void analisarConectividade(int u, int pai) {
    dfn[u] = minRach[u] = ++tempoGlobal;
    int filhosImediatos = 0;

    for (int i = primeiroNo[u]; i != 0; i = proximaAresta[i]) {
        int v = arr[vezinhos].destino;
        
        if (v != pai) { // Ignora a aresta de retorno direta para o pai
            if (!dfn[v]) {
                filhosImediatos++;
                analisarConectividade(v, u);
                minRach[u] = std::min(minRach[u], minRach[v]);

                // Critério para Ponto de Corte
                if (pai != 0 && minRach[v] >= dfn[u]) {
                    isCorte[u] = true;
                }
                
                // Critério para Ponte (Estritamente maior)
                if (minRach[v] > dfn[u]) {
                    pontesExistentes++;
                }
            } else {
                minRach[u] = std::min(minRach[u], dfn[v]);
            }
        }
    }
    
    // Caso especial para a Raiz
    if (pai == 0 && filhosImediatos >= 2) {
        isCorte[u] = true;
    }
}

Diferença entre Conectividade de Aresta e de Vértice

Dois vértices são considerados Bi-conexos por Aresta se, ao remover qualquer única aresta, eles permanecem conectados. Já a Bi-conexão por Vértice exige que eles permaneçam conectados mesmo após a remoção de qualquer único vértice intermediário.

A extração dos componentes bi-conexos pode ser feita simultaneamente à detecção de cortes usando uma pilha adicional. Quando detectamos minReach[v] >= dfn[u], sabemos que formamos um novo componente. Extrai-se os nós da pilha até encontrar v, mantendo u fora pois ele atua como conector entre múltiplos componentes.

Solução para Problemas de Escapamento (Minas)

Um cenário comum envolve determinar quantas saídas seguras são necessárias em diferentes componentes para garantir a fuga, considerando a possível falha de algumas estações (cortes). Se um componente Bi-conexo não contiver nenhum ponto de corte, duas saídas são ideais. Se tiver exatamente um ponto de corte, uma saída dentro do componente (diferente do corte) basta. O cálculo total combina essas possibilidades multiplicativas entre os componentes.

const int MAXN = 500005;
int n, m, cntEdges = 0;
int dfn[MAXN], low[MAXN], tempo = 0;
int pilha[MAXN], topoPilha = 0;
bool isCorte[MAXN];
std::vector<int> componentList[MAXN];
int dccCount = 0;
struct Aresta {
    int v, nxt;
};
Aresta arestas[MAXN << 2];
int primeira[MAXD];

void add(int u, int v) {
    arestas[++cntEdges] = {v, primeira[u]};
    primeira[u] = cntEdges;
}

void tarjanBCC(int u, int p) {
    dfn[u] = low[u] = ++tempo;
    pilha[++topoPilha] = u;
    bool temFilho = false;
    int filhoCnt = 0;

    for (int e = primeira[u]; e != 0; e = arestas[e].nxt) {
        int v = arestas[e].v;
        if (v == p) continue;
        
        if (!dfn[v]) {
            filhoCnt++;
            tarjanBCC(v, u);
            low[u] = std::min(low[u], low[v]);

            if (low[v] >= dfn[u]) {
                dccCount++;
                int cur = pilha[topoPilha--];
                do {
                    componentList[dccCount].push_back(cur);
                    if (cur == v) break; 
                    cur = pilha[topoPilha--];
                } while (false);
                componentList[dccCount].push_back(u);
            }
            
            if (low[v] >= dfn[u] && p != 0) {
                isCorte[u] = true;
            }
            temFilho = true;
        } else {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    // Verificação para nó raiz
    if (!p && !temFilho) {
         dccCount++;
         componentList[dccCount].push_back(u);
    }
    if (!p && filhoCnt >= 2) isCorte[u] = true;
}

int main() {
    // Leitura de N e M
    scanf("%d %d", &n, &m);
    // Inicialização...
    rep(i, 1, m) {
        int u, v; scanf("%d %d", &u, &v);
        add(u, v); add(v, u);
    }
    
    for(int i=1; i<=n; i++) {
        if(!dfn[i]) tarjanBCC(i, 0);
    }
    
    // Lógica de contagem final baseada nos componentes
    return 0;
}
</int>

Implementação Completa para Pontes

Para localizar especificamente as pontes (edges cuja remoção aumenta o número de componentes conexos), a verificação é mais restritiva. Apenas as arestas tree onde low[v] > dfn[u] são pontes reais. Arredondando esse algoritmo, podemos usar uma segunda busca (DFS) sobre os componentes restantes sem pontes para agrupar nós equivalentes.

void dfsPonte(int u, int rootId) {
    visitedComp[u] = rootId;
    for (int e = primeira[u]; e; e = arestas[e].nxt) {
        int v = arestas[e].v;
        if (isPonte[e]) continue; // Pula arestas bridge
        
        if (!visitedComp[v]) {
            dfsPonte(v, rootId);
        }
    }
}

Considerações Finais

A eficiência dessas técnicas reside na linearidade O(V+E), permitindo aplicações complexas em redes de grande escala onde a análise de redundância e resiliência é crítica.