Solução Informática – Nível Avançado – Semana 31

Escrito por Caique Paiva

Conhecimento Prévio Necessário

• Programação Dinâmica
• Componentes Fortemente Conexas

Veja que, dois vértices $u$ e $v$ são $p$-alcançáveis se e somente se eles estão na mesma componente fortemente conexa, e veja que podemos dividir o grafo em várias componentes conexas. Com isso, seja $dp(i)$ o menor número de vértices para criar um grafo $i$-alcançável. Então, temos que $dp(i) =$ min $(dp(i - \frac{s(s-1)}{2}) + s)$ com $s$ variando de modo que $\frac{s(s-1)}{2} \le i$, ou seja, $s$ é o tamanho de uma das componentes conexas. Essa $dp$ elas são calculadas em $O(p \sqrt{p})$ ($p$ elementos e $\sqrt{p}$ a transição).

Em todos os grafos $p$-alcançáveis com $dp(p)$ vértices, a cota de pares não-direcionados é $dp(p) \choose 2 - p$ porque nós temos exatamente $p$ pares de vértices que são alcançáveis de um para outro, ou seja, não são não-direcionados. Podemos conseguir essa cota com a seguinte construção: Seja $s_1, s_2, \cdots s_k$ uma sequência de componentes fortemente conexas que estão de acordo com os valores da $dp$. Faça a primeira componente conexa ter os vértices de $[1, s_1]$, a segunda os $[s1+1, s_1 + s_2]$ e assim vai. Ligamos uma aresta de $u$ para $v$ se $u < v$, sem contar as que já temos para fazer as componentes fortemente conexas serem fortemente conexas. Se repetir aresta, é só excluir uma das repetições

Segue o código para melhor entendimento (Link).