Wprawdzie moje rozwiązanie nie jest krytycznie różne od wzorcowego, ale wydaje mi się, że jest prostsze (używa jump pointerów i niczego więcej, poza wyznaczeniem początkowego grafu).

Jeśli z x woda kapie do y to tworzymy sobie skierowaną krawędź z x do y. Analogicznie jak w rozwiązaniu wzorcowym, mamy lewe i prawe krawędzie. Dodajemy sobie sztuczny odcinek na samym dole, żeby wszystkie ścieżki do niego prowadziły.

Zastanówmy się nad wierzchołkiem X, który ma lewe dziecko L i prawe dziecko R.
Główny pomysł jest taki, że na początku z wierzchołka X wychodzą dwie ścieżki, ale istnieje taki wierzchołek, że zarówno idąc na początku krawędzią w lewo, jak i w prawo, jesteśmy w stanie do niego dojść (takim wierzchołkiem na pewno jest sztuczna podłoga). Takich wierzchołków może być wiele, ale zauważmy, że z najwyższego z nich na pewno prowadzą ścieżki do wszystkich pozostałych. Jeśli znajdziemy ten najwyższy wierzchołek Y i wiemy już, że do naszego wierzchołka X da się dojść z k wierzchołków wyżej, to chcielibyśmy dodać k+1 wszystkim wierzchołkom osiągalnym z X. Dodajmy więc k+1 do L i R oraz odejmijmy k+1 w Y. W ten sposób robimy coś w stylu sum prefiksowych na drzewie.

Problemem pozostaje znalezienie tego wierzchołka Y. Będziemy chcieli użyć do tego jump pointerów. Zauważmy, że Y musi być osiągalny idąc jedynie w prawo z L i jedynie w lewo z R. Podobnie więc jak w jump pointerach będziemy się przemieszczać o potęgi dwójki po lewych i prawych krawędziach odpowiednich wierzchołków. Niech L i R utrzymują oddzielne zmienne (jump_L, jump_R), które mówią, który rozmiar skoku powinien być teraz rozpatrywany (2^jump_L, 2^jump_R). Załóżmy, że aktualne rozmiary skoków są za duże, tj skacząc o te wartości, ominęliśmy Y (łatwo to sprawdzić, dobry skok to taki, że R znajduje się całkowicie na prawo od L po skoku, złe skoki to wszystkie pozostałe). Ale problem jest taki, że nie wiemy, czy tylko jedna wartość jump jest za duża, czy obie. Ale na pewno za duża jest wartość jump tego wierzchołka, który po skoku wylądował niżej(!), możemy ją więc bezpiecznie zmniejszyć i kontynuować. Jest tu jeszcze kilka przypadków, ale znając ten najważniejszy fakt łatwo resztę wymyślić.

Ja mam tak samo pierwszą część, tylko tych dominatorów Y szukam w czasie liniowym, wykorzystując to, że graf jest planarny.

Identyfikuję ściany grafu z najwyższym wierzchołkiem tej ściany. Dla każdego wierzchołka (zaczynając od góry) liczę, jaką ma ścianę po lewej i jaką po prawej.

Teraz liczę dominatory, zaczynając od dołu. Żeby znaleźć dominatora Y wierzchołka X, muszę zacząć od lewego syna X i iść w prawo, i od prawego syna X i iść w lewo, aż te ścieżki się spotkają.

Więc po prostu idę w pętli, zawsze tym który jest wyżej.

Załóżmy że chcę pójść lewą ścianą w dół i jestem w wierzchołku v. Patrzę na numer ściany po prawej. Jeśli to jest X, to idę w prawo o jeden krok. Jeśli to jest ściana inna niż X, na przykład Z, to skaczę od razu do dominatora wierzchołka Z, który już był policzony wcześniej.

Razem to liczenie dominatorów ma złożoność O(n), bo każdą krawędzią pójdę tylko raz, i przeskok dla każdej ściany Z zrobię tylko raz.