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.
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']$:
O componente $C$ foi atingido primeiro. Isso significa que a dfs ocorre em algum vértice $v$ do componente $C$ em algum momento, mas todos os outros vértices dos componentes $C$ e $C'$ não foram visitados ainda. Por condição, existe uma aresta $(C, C')$ em um grafo de condensação, portanto, não apenas o componente inteiro $C$ é alcançável por $v$ mas todo o componente $C'$ também é alcançável. Isso significa que a dfs que está sendo executada a partir do vértice $v$ visitará todos os vértices dos componentes $C$ e $C'$, portanto, eles serão descendentes de $v$ na árvore da DFS, ou seja, para cada vértice $u \in C \cup C', u \ne v$ temos que $tout[v] > tout[u]$, como afirmamos.
Suponha que o componente $C'$ tenha sido visitado primeiro. Da mesma forma, a DFS ocorre em algum vértice $v$ do componente $C'$ em algum momento, mas todos os outros vértices dos componentes $C$ e $C'$ ainda não foram visitados. Mas, pela condição, existe uma aresta $(C, C')$ no grafo de condensação; portanto, devido à propriedade acíclica do grafo de condensação, não há caminho de retorno de $C'$ para $C$, ou seja, a dfs a partir do vértice $v$ não alcançará vértices de $C$. Isso significa que os vértices de $C$ serão visitados pela dfs depois, então $tout[C] > tout[C']$. Isso completa a prova.
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.
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.