Orientação forte

Uma "orientação forte" de um grafo não direcionado é uma atribuição de uma direção para cada aresta que o torna um grafo fortemente conectado. Ou seja, após a "orientação", poderemos visitar qualquer vértice de qualquer vértice seguindo as arestas direcionadas.

Solução

Obviamente, isso não pode ser feito em qualquer grafo. Considere uma ponte em um grafo. Temos que atribuir uma direção a ela e, dessa forma, tornamos essa ponte "cruzável" em apenas uma direção. Isso significa que não podemos ir de uma das extremidades finais da ponte para a outra, portanto, não podemos tornar o grafo fortemente conectado.

Agora, considere uma DFS sobre um grafo conexo sem pontes. Claramente, visitaremos cada vértice. E como não há pontes, podemos remover qualquer aresta da "árvore de travessia da DFS" e ainda podemos ir de "baixo" da aresta para "cima" da aresta usando um nó com um caminho que contenha pelo menos uma back edge(aresta de retorno). A partir disso, segue-se que a partir de qualquer vértice podemos ir para a raiz da árvore da DFS. Além disso, a partir da raiz da árvore da DFS, podemos visitar qualquer vértice que escolhermos. Encontramos uma forte orientação!

Em outras palavras, para orientar fortemente um grafo conexo sem pontes, executamos uma DFS nele e deixamos que as arestas da árvore da DFS apontem para longe da raiz da DFS e que todas as outras arestas apontem do descendente para o ancestral na árvore da DFS.

O resultado de que grafos conexos sem pontes são exatamente os grafos que têm orientações fortes é chamado de "Teorema de Robbins".

Extensão do problema

Vamos considerar o problema de encontrar uma orientação no grafo para que o número de componentes fortemente conectados seja mínimo.

Cada componente do grafo pode ser considerado separadamente. Agora, como apenas os grafos sem ponte são 'fortemente orientáveis', vamos remover todas as pontes temporariamente. Terminamos com um número de componentes sem pontes e sabemos que podemos orientar fortemente cada um deles.

Só podíamos orientar arestas, não removê-las, mas acaba que podemos orientar as pontes arbitrariamente. Claramente, a maneira mais fácil de orientá-los seria executar o algoritmo descrito acima sem modificações em cada componente conectado original.

Implementação

Aqui, a entrada é n — o número de vértices, m — o número de arestas, e então m linhas descrevendo as arestas.

A saída é o número mínimo de componentes fortemente conectados na primeira linha e na segunda linha uma string de m caracteres, > — nos dizendo que a aresta correspondente da entrada é orientada da esquerda para o vértice direito (como na entrada) , ou < — o oposto.

Este é um algoritmo de busca de pontes modificado para também orientar as arestas. Você também pode orientar as arestas como um primeiro passo e depois contar os componentes fortemente conectados no grafo orientado.

vector<vector<pair<int, int>>> adj; // lista de adjacência - pares vértice e aresta
vector<pair<int, int>> edges;

vector<int> tin, low;
int bridge_cnt;
string orient;
vector<bool> edge_used;
void find_bridges(int v) {
    static int time = 0;
    low[v] = tin[v] = time++;
    for (auto p : adj[v]) {
        if (edge_used[p.second]) continue;
        edge_used[p.second] = true;
        orient[p.second] = v == edges[p.second].first ? '>' : '<';
        int nv = p.first;
        if (tin[nv] == -1) { // se nv não tiver sido visitado ainda
            find_bridges(nv);
            low[v] = min(low[v], low[nv]);
            if (low[nv] > tin[v]) {
                // uma ponte entre v e nv
                bridge_cnt++;
            }
        } else {
            low[v] = min(low[v], low[nv]);
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    adj.resize(n);
    tin.resize(n, -1);
    low.resize(n, -1);
    orient.resize(m);
    edges.resize(m);
    edge_used.resize(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        edges[i] = {a, b};
    }
    int comp_cnt = 0;
    for (int v = 0; v < n; v++) {
        if (tin[v] == -1) {
            comp_cnt++;
            find_bridges(v);
        }
    }
    printf("%d\n%s\n", comp_cnt + bridge_cnt, orient.c_str());
}

Problemas