Ordenação Topológica

Seja um grafo direcionado com $n$ vértices e $m$ arestas. Você precisa numerar os vértices para que cada aresta seja direcionada de um vértice com um número menor atribuído a um vértice com um número maior.

Em outras palavras, você deseja encontrar uma permutação dos vértices (ordem topológica) que corresponde à ordem definida por todas as arestas do grafo.

A ordem topológica pode não ser única (por exemplo, se o grafo estiver vazio; ou se existirem três vértices $a$, $b$ e $c$ para os quais existem caminhos de $a$ para $b$ e de $a$ para $c$, mas não caminhos de $b$ a $c$ ou de $c$ a $b$).

A ordem topológica pode não existir se o grafo contiver ciclos (porque há uma contradição: existe um caminho de $a$ para $b$ e vice-versa).

Um problema comum em que a ordenação topológica ocorre é o seguinte. Existem $n$ variáveis com valores desconhecidos. Para algumas variáveis, sabemos que uma delas é menor que a outra. Você deve verificar se essas restrições são contraditórias e, se não, gerar as variáveis ​​em ordem crescente (se várias respostas forem possíveis, gerar uma delas). É fácil perceber que esse é exatamente o problema de encontrar a ordem topológica de um grafo com $n$ vértices.

Algoritmo

Para resolver esse problema, usaremos uma DFS.

Vamos supor que o grafo seja acíclico, ou seja, existe uma solução. O que a DFS faz? Quando iniciado a partir de algum vértice $v$, ele tenta executar todas as arestas saindo de $v$. Ela falha ao percorrer as arestas pelas quais as extremidades opostas foram visitadas anteriormente, e percorre as demais arestas começando a partir das extremidades.

Assim, no momento em que a chamada $dfs(v)$ termina, todos os vértices que podem ser acessados ​​a partir de $v$, diretamente (através de uma aresta) ou indiretamente, já foram visitados pela busca. Portanto, se no momento da saída de $dfs(v)$ adicionarmos o vértice $v$ ao início de uma determinada lista, no final, essa lista armazenará uma ordem topológica de todos os vértices.

Essas explicações também podem ser apresentadas em termos dos tempos de saída da rotina da DFS. O tempo de saída do vértice $v$ é o momento em que $dfs(v)$ terminou de ser executada (os tempos podem ser numerados de $1$ a $n$). É fácil entender que o tempo de saída de qualquer vértice $v$ é sempre maior que o tempo de saída de qualquer vértice acessível a partir dele (desde que eles sejam visitados antes da chamada $dfs(v)$ ou durante ela). Assim, a ordem topológica desejada é ordenar os vértices em ordem decrescente dos seus tempos de saída.

Implementação

Aqui está uma implementação que assume que o grafo é acíclico, ou seja, a ordem topológica desejada existe. Se necessário, você pode facilmente verificar se o grafo é acíclico, conforme descrito no artigo sobre a DFS.

int n; // número de vértices
vector<vector<int>> adj; // lista de adjacência do grafo
vector<bool> visited;
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
    reverse(ans.begin(), ans.end());
}

A principal função da solução é topological_sort, que inicializa as variáveis da ​​DFS e executa a DFS; a resposta é recebida no vetor ans.

Problemas