Componentes fortemente conectados
Construindo um grafo de condensação

Definições

Você recebe um grafo direcionado $G$ com vértices $V$ e arestas $E$. É possível que haja loops e arestas múltiplas. Vamos denotar $n$ como número de vértices e $m$ como número de arestas em $G$.

Um componente fortemente conectado é um subconjunto de vértices $C$ de modo que quaisquer dois vértices desse subconjunto sejam alcançáveis um pelo outro, ou seja, para qualquer $u, v \in C$: $$ u \mapsto v, v \mapsto u $$ onde $\mapsto$ significa que é alcançável, ou seja, existência do caminho do primeiro vértice ao segundo.

Componentes fortemente conectados não se cruzam, ou seja, isto é uma partição de todos os vértices do grafo. Assim, podemos dar uma definição para um grafo de condensação $G^{SCC}$ como um grafo contendo todos os componentes fortemente conectados como um vértice. Cada vértice do grafo de condensação corresponde ao componente fortemente conectado do grafo $G$. Existe uma aresta orientada entre dois vértices $C_i$ e $C_j$ do grafo de condensação se e somente se houver dois vértices $u \in C_i, v \in C_j$ de modo que exista uma aresta no grafo inicial, ou seja, $(u, v) \in E$.

A propriedade mais importante do grafo de condensação é que ele é acíclico. De fato, suponha que haja uma aresta entre $C$ e $C'$, vamos provar que não há aresta de $C'$ para $C$. Suponha que $C' \mapsto C$. Assim, existem dois vértices $u' \in C$ e $v' \in C'$ de modo que $v' \mapsto u'$. Mas como $u$ e $u'$ estão no mesmo componente fortemente conectado, há um caminho entre eles; o mesmo para $v$ e $v'$. Como resultado, se juntarmos esses caminhos, teremos que $v \mapsto u$ e ao mesmo tempo, $u \mapsto v$. Portanto, $u$ e $v$ deveriam estar no mesmo componente fortemente conectado, portanto, isso é uma contradição. Assim, isso completa a prova.

O algoritmo descrito na próxima seção extrai todos os componentes fortemente conectados em um determinado grafo. E então fica mais fácil de construir um grafo de condensação.

Descrição

O algoritmo descrito foi sugerido de forma independente por Kosaraju e Sharir em 1979. Esse é um algoritmo mais fácil de implementar, ele é baseado em duas séries de DFS, levando tempo $O(n + m)$.

Na primeira etapa do algoritmo, estamos realizando uma sequência de buscas em profundidade, visitando o grafo inteiro. Começamos em cada vértice do grafo e executamos uma DFS de cada vértice não visitado. Para cada vértice, estamos acompanhando o tempo de saída $tout[v]$. Esses tempos de saída têm um papel fundamental no algoritmo e isso é expresso no próximo teorema.

Primeiro, vamos fazer anotações: vamos definir o tempo de saída $tout[C]$ do componente fortemente conectado $C$ como o máximo dos valores $tout[v]$ para todos os $v \in C$. Além disso, durante a prova do teorema, mencionaremos os tempos de entrada $tin[v]$ em cada vértice e da mesma maneira considerar $tin[C]$ para cada componente fortemente conectado $C$ como mínimo dos valores $tin[v]$ para todos os $v \in C$.

Teorema. Seja $C$ e $C'$ dois componentes fortemente conectados diferentes e há uma aresta $(C, C')$ em um grafo de condensação entre esses dois vértices. Então $tout[C] > tout[C']$.

Existem dois casos diferentes principais na prova, dependendo de qual componente será visitado pela DFS primeiro, ou seja, irá depender da diferença entre $tin[C]$ e $tin[C']$:

A prova é a base do algoritmo para encontrar componentes fortemente conectados. Segue-se que qualquer aresta $(C, C')$ no grafo de condensação vem de um componente com um valor maior de $tout$ para um componente com um valor menor.

Se ordenarmos todos os vértices $v \in V$ por ordem decrescente do tempo de saída $tout[v]$, então, o primeiro vértice $u$ será um vértice do componente fortemente conectado da "raiz", ou seja, um vértice em que nenhuma aresta no grafo de condensação alcança/chega até ele. Agora, queremos executar essa busca nesse vértice $u$ para que ele visite todos os vértices desse componente fortemente conectado, mas não outros; fazendo isso, podemos gradualmente selecionar todos os componentes fortemente conectados: vamos remover todos os vértices correspondentes ao primeiro componente selecionado e, em seguida, vamos encontrar um vértice com o maior valor de $tout$, executar essa busca nele e assim por diante.

Vamos considerar o grafo transposto $G^T$, ou seja, o grafo recebido de $G$ porém, alterando a direção de cada aresta no sentido oposto. Obviamente, este grafo terá os mesmos componentes fortemente conectados, como um grafo inicial. Além disso, o grafo de condensação $G^{SCC}$. Isso significa que não haverá arestas do nosso componente "raiz" para outros componentes.

Portanto, para visitar todo o componente "raiz" fortemente conectado, contendo o vértice $v$, é suficiente executar uma busca a partir do vértice $v$ no grafo $G^T$. Essa busca visitará todos os vértices desse componente fortemente conectado e apenas eles. Como mencionado anteriormente, podemos remover esses vértices do grafo e encontrar o próximo vértice com um valor máximo de $tout[v]$ e executar a busca no grafo transposto a partir dele, e assim por diante.

Assim, criamos o próximo algoritmo para selecionar componentes fortemente conectados:

1º passo. Execute uma sequência de dfs do grafo $G$ que retornará vértices em ordem crescente dos tempos de saída $tout$, ou seja, uma lista $order$.

2º passo. Construa o grafo transposto $G^T$. Execute uma série de (dfs/bfs)'s na ordem determinada pela lista $order$ (para ser exato na ordem inversa, ou seja, na ordem decrescente dos tempos de saída). Todo conjunto de vértices, alcançado após a próxima busca, será o próximo componente fortemente conectado.

O comportamento assintótico do algoritmo é $O(n + m)$, porque são apenas as duas dfs's ou bfs's.

Finalmente, é apropriado mencionar a ordenação topológica aqui. Primeiro, a etapa 1 do algoritmo representa a ordenação topológica invertida do grafo $G$ (na verdade, é exatamente isso que a ordenação dos vértices pelos tempos de saída significa). Em segundo lugar, o esquema do algoritmo gera componentes fortemente conectados em ordem decrescente de seus tempos de saída, gerando componentes - vértices do grafo de condensação/condensado - na ordem da ordenação topológica.

Implementação

    vector < vector<int> > g, gr;
    vector<bool> used;
    vector<int> order, component;

    void dfs1 (int v) {
        used[v] = true;
        for (size_t i=0; i<g[v].size(); ++i)
            if (!used[ g[v][i] ])
                dfs1 (g[v][i]);
        order.push_back (v);
    }

    void dfs2 (int v) {
        used[v] = true;
        component.push_back (v);
        for (size_t i=0; i<gr[v].size(); ++i)
            if (!used[ gr[v][i] ])
                dfs2 (gr[v][i]);
    }

    int main() {
        int n;
        ... lendo n ...
        for (;;) {
            int a, b;
            ... lendo próxima aresta (a,b) ...
            g[a].push_back (b);
            gr[b].push_back (a);
        }

        used.assign (n, false);
        for (int i=0; i<n; ++i)
            if (!used[i])
                dfs1 (i);
        used.assign (n, false);
        for (int i=0; i<n; ++i) {
            int v = order[n-1-i];
            if (!used[v]) {
                dfs2 (v);
                ... printando próximo componente ...
                component.clear();
            }
        }
    }

Aqui, $g$ é o grafo e $gr$ é o grafo transposto. A função $dfs1$ implementa a busca em profundidade no grafo $G$, $dfs2$ - no grafo transposto $G^T$. A função $dfs1$ preenche a lista $order$ com vértices na ordem crescente de seus tempos de saída (na verdade, ele está fazendo uma ordenação topológica). A função $dfs2$ armazena todos os vértices alcançados na lista $component$, isso irá armazenar o próximo componente fortemente conectado após cada execução.

Literatura

Problemas