Primeiramente, note que o grafo é uma árvore. Se quisermos todos os caminhos que passam por determinado tipo de aresta, eliminamos todas essas arestas e nos restará uma floresta (várias componentes conexas e cada uma é uma árvore). Então, fica fácil ver que os caminhos que passam por um tipo de aresta são os caminhos entre vértices de componentes conexas distintas.
Seja $$k$$ o número de componentes conexas e $$c_1$$, $$c_2$$, …, $$c_k$$ o número de vértices em cada uma delas. Queremos, então, a soma dos produtos dois a dois dos $$c_i$$’s. Para fazer isso de maneira linear (quadrática estouraria o tempo!), usamos o fato de que:
$$!(c_1 + c_2 + … + c_k)^2 = (c_1^2 + c_2^2 + … + c_k^2) + 2(c_1 c_2 + c_1 c_3 + … + c_2 c_3 + … + c_{k-1} c_k)$$
e podemos calcular os dois primeiros termos de maneira linear.
Para calcular os $$c_i$$’s. podemos fazer um algoritmo de Flood Fill ou Union Find (vide as aulas do Curso Noic).
O código, então, fica:
https://gist.github.com/luccasiau/2465e35bb63ba427bebb
Deixe um comentário