Zadania podobne, lecz różnią się w najważniejszej kwestii.
W tym zadaniu mamy do czynienia z drzewem, co znacząco ułatwia znalezienie rozwiązania. W moim zadaniu mamy do czynienia z multigrafem. Tak na prawdę problem, który zaproponowałem jest znanym problemem NP-trudnym o nazwie Vertex Cover ( en.wikipedia.org/wiki/Vertex_cover), którego najlepsze znane rozwiązanie ma złożoność wykładniczą, co oznacza, że żeby rozwiązać je dla [tex]n = 10^5[/tex] trzeba napisać jakąś heurystykę.
Identyczne zadanie dla mniejszego [tex]n[/tex] można znaleźć tu: pl.spoj.com/problems/AL_18_10/