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).