Solução por Lúcio Figueiredo
Conhecimento prévio necessário:
Seja $$G$$ um grafo que possui $$N$$ vértices e $$M$$ arestas direcionadas, formadas ao ligar os dois vértices $$u_i$$ e $$v_i$$ de cada pedido $$i$$. Defina o grafo $$G’$$ como um grafo que usa a menor quantidade de arestas direcionadas necessárias de modo a satisfazer todos os pedidos.
Defina componente fracamente conexa como um conjunto de vértices em um grafo direcionado tal que, para cada par de vértices $$(u, v)$$ na mesma componente, existe um caminho de $$u$$ para $$v$$ ou de $$v$$ para $$u$$.
Perceba que, para cada pedido $$(u, v)$$, os vértices $$u$$ e $$v$$ estão na mesma componente fracamente conexa em $$G$$ e em $$G’$$. Logo, os vértices de cada componente fracamente conexa de $$G’$$ são formados pela união de vértices de componentes fracamente conexas em $$G$$.
Vamos assumir que $$G’$$ possui as mesmas componentes fracamente conexas que $$G$$, ou seja, que nenhuma união de componentes foi realizada. Iremos provar, posteriormente, que não é ótimo realizar a união de componentes de $$G$$ para formar $$G’$$. Vamos, então, calcular o número mínimo de arestas necessárias em cada componente de $$G’$$, analisando as componentes de $$G$$.
Para cada componente $$C$$ de $$G$$, vamos analisar dois casos:
Caso 1: $$C$$ é acíclica. Neste caso, vamos realizar uma ordenação topológica em $$C$$. Seja $$topo[i]$$ tal ordenação topológica, onde $$topo[i]$$ é o $$i$$-ésimo vértice na ordenação. Se criarmos uma aresta indo de $$topo[i]$$ para $$topo[i+1]$$ para $$1 \leq i < |C|$$, conseguimos realizar todos os pedidos na componente, já que para todo pedido $$(u_i, v_i)$$, $$u_i$$ possui índice menor que $$v_i$$ na ordenação topológica. Logo, conseguimos satisfazer os pedidos nesta componente com $$|C|-1$$ arestas, que é um valor ótimo, já que a quantidade mínima de arestas em uma componente fracamente conexa $$C$$ é $$|C|-1$$.
Caso 2: $$C$$ possui um ciclo. Neste caso, perceba que a quantidade mínima de arestas necessárias é $$|C|$$, já que toda componente fracamente conexa cíclica possui pelo menos $$|C|$$ arestas. Assim, podemos simplesmente ligar os vértices de $$C$$ em um “círculo”; ou seja, sendo $$c_1, c_2, …, c_{|C|}$$ os vértices de $$C$$, podemos simplesmente criar uma aresta de $$c_i$$ para $$c_{i+1}$$ para todo $$i < |C|$$ e uma aresta adicional de $$c_{|C|}$$ para $$c_1$$. Desta forma, com $$|C|$$ arestas, ligamos os vértices da componente de forma que todo vértice consegue alcançar qualquer outro vértice da componente, e portanto, todos os pedidos serão satisfeitos.
Usando as observações já feitas, concluímos que o número mínimo de arestas em $$G’$$ é igual a $$\sum_C^{} |C| – f(C)$$, onde o somatório percorre todas as componentes fracamente conexas de $$G$$ e $$f(C)$$ é igual a $$1$$ se $$C$$ é acíclica e $$0$$ caso contrário.
No entanto, as observações acima assumem que nenhuma componente de $$G’$$ será formada pela união de componentes de $$G$$. Provaremos a seguir que, de fato, nunca é ótimo unir duas componentes de $$G$$ para formar $$G’$$.
Prova: Vamos realizar uma prova por absurdo, ou seja, suponha que existem componentes fracamente conexas $$C_1, C_2, …, C_k$$ em $$G$$ tal que é ótimo unir os vértices em tais componentes para formar alguma componente fracamente conexa em $$G’$$. Vamos dividir a prova em dois casos:
Caso 1: Nenhuma das componentes $$C_i$$ ($$1 \leq i \leq k$$) possui um ciclo. Neste caso, ao unir as componentes $$C_1, C_2, …, C_k$$, a componente resultante possuirá $$S = |C_1| + |C_2| + … + |C_k|$$ vértices. Logo, como a componente será acíclica, concluímos que a quantidade mínima de arestas que satisfazem os pedidos desta nova componente é $$S-1$$. Por outro lado, caso esta união não fosse realizada, a quantidade total de arestas necessárias para cada componente seria igual a $$(|C_1|-1) + (|C_2|-1) + … + (|C_k|-1) = S – k$$, que é estritamente menor que $$S-1$$. Logo, chegamos em um absurdo.
Caso 2: Alguma das componentes de $$C_i$$ ($$1 \leq i \leq k$$) possui um ciclo. Neste caso, ao unir as componentes $$C_1, C_2, …, C_k$$, a componente resultante possuirá $$S = |C_1| + |C_2| + … + |C_k|$$ vértices. Como a componente possuirá um ciclo, a quantidade mínima de arestas que satisfazem os pedidos desta nova componente é $$S$$. Por outro lado, caso esta união não fosse realizada, a quantidade total de arestas necessárias para cada componente seria igual a $$(|C_1| – f(C_1)) + (|C_2| – f(C_2)) + … + (|C_k| – f(C_k)) = S – f(C_1) – f(C_2) – … – f(C_k)$$, que é menor ou igual a $$S$$. Logo, chegamos em um absurdo, pois realizar a união não reduzirá a quantidade de arestas necessárias em $$G’$$.
Logo, provamos a afirmação de que não é ótimo realizar a união de componentes de $$G$$ para formar $$G’$$.
A complexidade final da solução é $$O(N+M)$$, pois conseguimos encontrar componentes fracamente conexas utilizando DFSs, e para checar se uma componente é acíclica, podemos verificar se existe uma ordenação topológica em tal componente.
Confira o código para melhor entendimento: