Solução Informática - Nível Avançado - Semana 4

Solução por Lúcio Figueiredo

Conhecimento prévio necessário:

• Conceitos de Grafos
• DFS
• Ordenação Topológica

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: