Componentes Fortemente Conexos

O algoritmo de Tarjan identifica componentes fortemente conexos (SCCs) em um grafo direcionado, permitindo a condensação subsequente. Utilizamos uma busca em profundidade (DFS) para construir uma árvore DFS, atribuindo a cada vértice u um tempo de descoberta ordem[u] e um valor menor[u] que representa o mener tempo acessível a partir de u.

Durante a DFS, ao explorar uma aresta de u para v: - Se v não foi visitado, realizamos a DFS recursivamente e atualizamos menor[u] = min(menor[u], menor[v]). - Se v já foi visitado e está na pilha de recursão, atualizamos menor[u] = min(menor[u], ordem[v]).

Quando menor[u] == ordem[u], u é a raiz de um SCC. Todos os vértices na pilha acima de u até u inclusive formam esse componente.

void dfsTarjan(int v) {
    visitado[v] = true;
    ordem[v] = menor[v] = ++tempo;
    pilha[++topo] = v;
    for (int w : adjacencias[v]) {
        if (ordem[w] == 0) {
            dfsTarjan(w);
            menor[v] = min(menor[v], menor[w]);
        } else if (visitado[w]) {
            menor[v] = min(menor[v], ordem[w]);
        }
    }
    if (menor[v] == ordem[v]) {
        totalSCCs++;
        while (true) {
            int w = pilha[topo--];
            visitado[w] = false;
            sccAtual.push_back(w);
            if (w == v) break;
        }
        sort(sccAtual.begin(), sccAtual.end());
        listaSCCs.push_back(sccAtual);
        sccAtual.clear();
    }
}

Condensação de Grafos

Após identiifcar os SCCs, podemos condensá-los em vértices únicos, transformando o grafo original em um grafo acíclico direcionado (DAG). Cada SCC é tratado como um nó, e as arestas entre SCCs são mantidas, removendo arestas dentro do mesmo componente.

Para implementar a condensação, atribuímos a cada vértice o identificador do seu SCC e reconstruímos o grafo com arestas entre SCCs distintos. Em seguida, podemos realizar operações como busca topológica ou programação dinâmica no DAG resultante.

vector<int> adjacenciasCondensadas[MAX_NOS];
int valorTotal[MAX_SCCS];
int pertenceAScc[MAX_NOS];

void condensarGrafo(int n) {
    for (int i = 1; i <= n; i++) {
        valorTotal[pertenceAScc[i]] += valorOriginal[i];
    }
    for (auto aresta : arestasOriginais) {
        int sccU = pertenceAScc[aresta.origem];
        int sccV = pertenceAScc[aresta.destino];
        if (sccU != sccV) {
            adjacenciasCondensadas[sccU].push_back(sccV);
            grauEntrada[sccV]++;
        }
    }
}

Componentes Biconexos de Arestas

Em grafos não direcionados, um componente biconexo de arestas é um subgrafo maximal sem arestas de corte. Para encontrá-los, adaptamos o algoritmo de Tarjan, rastreando a aresta percorrida em vez do vértice pai para lidar com arestas múltiplas e auto-loops.

Durante a DFS, ignoramos a aresta de volta direta, e ao detectar menor[v] == ordem[v], extraímos um componente biconexo de arestas da pilha.

void dfsBiconexo(int v, int arestaAnterior) {
    visitado[v] = true;
    ordem[v] = menor[v] = ++tempo;
    pilhaVertices[++topo] = v;
    for (int i = 0; i < adjacencias[v].size(); i++) {
        int w = adjacencias[v][i];
        int aresta = indicesArestas[v][i];
        if (aresta == arestaAnterior ^ 1) continue; // Ignorar aresta de volta
        if (ordem[w] == 0) {
            dfsBiconexo(w, aresta);
            menor[v] = min(menor[v], menor[w]);
        } else if (visitado[w]) {
            menor[v] = min(menor[v], ordem[w]);
        }
    }
    if (menor[v] == ordem[v]) {
        totalComponentes++;
        while (true) {
            int w = pilhaVertices[topo--];
            visitado[w] = false;
            componenteAtual.push_back(w);
            if (w == v) break;
        }
        listaComponentes.push_back(componenteAtual);
        componenteAtual.clear();
    }
}

Vértices de Corte

Um vértice u é um vértice de corte (ponto de articulação) se, na árvore DFS, existe um filho v tal que menor[v] >= ordem[u]. Para a raiz da DFS, é um vértice de corte se tiver pelo menos dois filhos.

Arestas de Corte

Uma aresta (u, v) é uma aresta de corte se, na árvore DFS, menor[v] > ordem[u]. Isso indica que não há caminho alternatiov de v para ancestrais de u.