Omówienie zadania Turysta (I etap XXIV OI)

Rozwiązanie wolne \(O(n \cdot n!)\)

Najpierw opiszemy rozwiązanie wolne, które jest bardzo intuicyjne. Otóż, rozważmy każdą permutację \(n\) miast. Dla danej permutacji zakładamy, że pierwsze miasto jest miastem startowym. Następnie przechodzimy do kolejnego miasta z permutacji, jeśli droga pomiędzy nimi ma odpowiedni kierunek. Tę czynność powtarzamy dopóki nie trafimy na drogę w przeciwnym kierunku. W ten sposób, dla badanej permutacji wybraliśmy najdłuższy jej poprawny początkowy fragment. Wynikiem dla danego wierzchołka jest najdłuższy taki poprawny fragment, spośród wszystkich permutacji o początku w rozważanym wierzchołku.

Wszystkich permutacji jest \(n!\), sprawdzenie każdej z nich wymaga \(O(n)\) operacji, zatem rozwiązanie działa w czasie \(O(n \cdot n!)\).

Początkowe spostrzeżenia i rozwiązanie wolne

Ścieżką Hamiltona w grafie nazywamy ścieżkę odwiedzającą wszystkie wierzchołki, każdy po razie. Turniejem nazywamy dowolny graf skierowany, w którym między każdą parą wierzchołków znajduje się dokładnie jedna krawędź.

Zadanie opisane w języku teorii grafów brzmi następująco: dany jest turniej i chcemy dla każdego wierzchołka wyznaczyć najdłuższą ścieżkę z niego wychodzącą. W szczególności odpowiedź na takie zadanie zawiera w sobie informację, które wierzchołki są początkami ścieżki Hamiltona. Zastanówmy się zatem nad prostszym zadaniem, polegającym na wyznaczeniu wierzchołków będących początkami ścieżki Hamiltona.

Twierdzenie. Wierzchołek \(p\) jest początkiem ścieżki Hamiltona w turnieju wtedy i tylko wtedy, gdy wszystkie pozostałe wierzchołki są z niego osiągalne.

Dowód. Algorytm wzorcowy, który przedstawimy później, będzie sam w sobie dowodem tego faktu. Jednak teraz przedstawimy alternatywny, krótszy dowód.

Oczywistym jest, że jeżeli dla pewnego wierzchołka \(u\) nie istnieje ścieżka od \(p\) do \(u\), to nie istnieje także ścieżka Hamiltona zaczynająca się w \(p\) (bo w szczególności taka ścieżka nie odwiedziłaby \(u\)). Pozostaje nam zatem wykazać, że jeżeli z \(p\) da się osiągnąć wszystkie inne wierzchołki, to istnieje ścieżka Hamiltona, która się w nim rozpoczyna.

Zatem, od teraz zakładamy, że \(p\) jest wierzchołkiem turnieju, z którego są osiągalne wszystkie wierzchołki. Uruchommy przeszukiwanie wszerz (DFS) z tego wierzchołka. Niech \(h = (v_1, v_2, \ldots, v_n)\) oznacza wierzchołki w malejącej kolejności czasów wyjścia (postorder). Okazuje się, że \(h\) jest szukaną ścieżką Hamiltona. Z definicji mamy, że \(v_1 = p\) (korzeń drzewa ma najpóźniejszy czas wyjścia). Udowodnimy teraz, że dla każdego \(i \in \{1, 2, \ldots, n - 1\}\), istnieje krawędź \((v_i, v_{i+1})\). Weźmy dowolne \(i \in \{1, 2, \ldots, n - 1\}\). Jeśli \(v_i\) ma jakieś dziecko w drzewie DFS, to jego poprzednikiem \(v_{i+1}\) w kolejności postorder jest ostatnie odwiedzone dziecko, zatem istnieje krawędź \((v_i, v_{i+1})\). Jeśli zaś \(v_i\) nie ma dzieci w drzewie DFS, to znaczy, że jest liściem. Zatem, w szczególności \(v_{i+1}\) nie leży w poddrzewie ukorzenionym w \(v_i\). Oczywiście także \(v_i\) nie leży w poddrzewie ukorzenionym w \(v_{i+1}\), ponieważ wtedy to \(v_{i}\) byłoby wcześniej w kolejności postorder. Skoro jednak \(v_i\) nie leży w poddrzewie ukorzenionym w \(v_{i+1}\), to znaczy, że nie istnieje krawędź \((v_{i+1}, v_i)\). Jednak mamy do czynienia z turniejem, więc istnieje krawędź \((v_i, v_{i+1})\). \(\square\)

Na podstawie tego twierdzenia możemy zaprojektować algorytm działający w złożoności czasowej \(O(n^3)\). Otóż, z każdego wierzchołka uruchamiamy przeszukiwanie DFS i wypisujemy odwiedzone wierzchołki w malejącej kolejności postorder. Oczywiście najdłuższa ścieżka wychodząca z wierzchołka nie może mieć w sobie żadnego wierzchołka nieosiągalnego z jej początku, co w połączeniu z twierdzeniem dowodzi poprawności tego algorytmu.

Podział turnieju na silnie spójne składowe

Zanim przejdziemy do pełnego rozwiązania, postawmy sobie łatwiejszy cel. A mianowicie, dla każdego wierzchołka chcemy policzyć (w złożoności czasowej \(O(n^2)\)), z ilu wierzchołków będzie składała się najdłuższa ścieżka z niego wychodząca. Już wiemy, jako wniosek z powyższego twierdzenia, że jest to równe liczbie wierzchołków osiągalnych z tego wierzchołka.

Przypomnijmy pojęcie silnie spójnej składowej. Dla dowolnego grafu skierowanego \(G\), silnie spójna składowa to taki podzbiór wierzchołków, że dla dowolnych dwóch wierzchołków \(u\) i \(v\) tej składowej istnieje ścieżka z \(u\) do \(v\) i z \(v\) do \(u\). Jest jasne, że jeżeli przedstawiony warunek wzajemnej osiągalności jest spełniony dla pary \((u, v)\) oraz dla pary \((v, t)\), to jest on także spełniony dla pary \((u, t)\), co dowodzi, że jest to poprawna definicja podziału wierzchołków dowolnego grafu. Po zdefiniowaniu takiego pojęcia możemy także zdefiniować graf silnie spójnych składowych grafu \(G\), którego wierzchołkami będą silnie spójne składowe \(G\). Krawędź pomiędzy dwoma wierzchołkami odpowiadającymi dwóm silnie spójnym składowym \(A\) i \(B\) istnieje, jeżeli w \(G\) jest krawędź \((a,b)\) dla jakichś wierzchołków \(a \in A\) i \(b \in B\). Zauważmy, że graf silnie spójnych składowych jest acykliczny. Ponadto, skoro w turnieju istnieje krawędź pomiędzy każdą parą wierzchołków, to graf silnie spójnych składowych turnieju także będzie turniejem. Stąd wniosek, że graf silnie spójnych składowych będzie acyklicznym turniejem. Wiadomo, że dla każdego acyklicznego turnieju składającego się z \(k\) wierzchołków da się je uporządkować w taki ciąg \(v_1, \ldots, v_k\), że krawędź pomiędzy \(v_i\) i \(v_j\) prowadzi od \(v_i\) do \(v_j\) wtedy i tylko wtedy, gdy \(i < j\) (jest to tzw. porządek topologiczny). Zatem możemy silnie spójne składowe naszego turnieju oznaczyć jako \(S_1, \ldots, S_k\) w taki sposób, że dla każdej pary \(1 \le i \le j \le k\), każdy wierzchołek z \(S_j\) jest osiągalny z każdego wierzchołka z \(S_i\). Ponadto, gdy \(i \neq j\), to istnieje krawędź od wierzchołka z \(S_i\) do tego z \(S_j\). Stąd, jeżeli \(v \in S_i\), to zbiór wierzchołków osiągalnych z \(v\) to \(S_i \cup \ldots \cup S_k\). Zatem długość najdłuższej ścieżki wychodzącej z \(v\) (liczonej w wierzchołkach) to \(|S_i| + \ldots + |S_k|\). Po wyznaczeniu podziału na silnie spójne składowe jest to proste do obliczenia w czasie \(O(n)\).

Jak wykorzystać fakt obcowania z turniejem przy podziale na silnie spójne składowe?

Ta sekcja jest ciekawą dygresją.

Znany jest algorytm podziału dowolnego grafu na silnie spójne składowe, działający w złożoności liniowej od rozmiaru grafu. Oczywiście jak najbardziej możemy go zastosować w tym zadaniu. Warto jedynie zdać sobie sprawę z tego, że złożoność liniowa oznacza złożoność liniową od liczby krawędzi, tzn. \(O(n^2)\) w naszym przypadku.

Okazuje się jednak, że aby wyznaczyć podział turnieju na silnie spójne składowe nie trzeba znać całego grafu, a jedynie liczbę krawędzi wychodzących z każdego wierzchołka! Jako że jest to dygresja, to pozostawiamy ten fakt do przemyślenia Czytelnikowi. W ramach ćwiczeń proponujemy zmierzyć się z zadaniem „Johnny" z pierwszej edycji konkursu Distributed Code Jam. Mniej związane z turniejami, ale w podobnych klimatach jest także zadanie „Konspiracja" z I etapu XVIII OI, w którym również wystarczy znać stopnie wierzchołków, aby je rozwiązać.

Cykle Hamiltona i wróżka na ratunek!

Przywołamy teraz kolejny fakt, który przyda nam się w rozwiązaniu. Okazuje się, że w każdym silnie spójnym turnieju (tzn. takim, w którym każdy wierzchołek jest osiągalny z każdego) istnieje cykl Hamiltona, tzn. cykl prosty zawierający wszystkie wierzchołki. Załóżmy na chwilę, że mamy dostęp do wróżki, której możemy przekazać silnie spójny turniej, a ona wskazuje w nim cykl Hamiltona. Z jej pomocą rozwiążemy zadanie.

Załóżmy, że na wejściu otrzymaliśmy silnie spójny turniej, a wróżka wskazała nam w nim cykl Hamiltona \(v_1, \ldots, v_n\). Zauważmy, że ścieżkę Hamiltona wychodzącą z wierzchołka \(v_i\) możemy wyprodukować poprzez obejście wierzchołków z tego cyklu zaczynając od \(v_i\), tzn. \(v_i v_{i+1} \ldots v_n v_1 \ldots v_{i-1}\).

Niestety nasz turniej nie musi być silnie spójny, zatem załóżmy, że \(S_1, \ldots, S_k\) to ciąg jego silnie spójnych składowych w porządku topologicznym. Użyjmy wróżki do poznania cykli \(C_1, \ldots, C_k\), gdzie \(C_i\) to cykl Hamiltona dla silnie spójnego turnieju wyznaczonego przez wierzchołki \(S_i\). Jeżeli teraz chcemy poznać najdłuższą prostą ścieżkę wychodzącą z wierzchołka \(v \in S_i\), to możemy najpierw obejść cykl \(C_i\) zaczynając od \(v\), przejść do dowolnego wierzchołka z \(S_{i+1}\), obejść cykl \(C_{i+1}\) zaczynając od tego wierzchołka, przejść do dowolnego wierzchołka z \(S_{i+2}\) itd. W taki sposób możemy rozwiązać zadanie, o ile tylko mamy dostęp do wróżki z wspomnianymi umiejętnościami.

Pozostaje nam zatem jedynie dowiedzieć się, jak możemy zaimplementować taką wróżkę.

Wyznaczanie podziału na silnie spójne składowe wraz z cyklami Hamiltona

W tej sekcji opiszemy jak podzielić turniej na silnie spójne składowe oraz jak zaimplementować wróżkę znajdującą cykl Hamiltona w silnie spójnym turnieju.

Zrobimy to w sposób inkrementalny. Niech \(T_q\) oznacza turniej złożony z pierwszych \(q\) wierzchołków naszego grafu. Założymy, że mamy turniej \(T_q\) podzielony na silnie spójne składowe wraz z cyklami Hamiltona wewnątrz nich. Jeżeli jakaś składowa składa się z jednego wierzchołka, to za dany cykl Hamiltona uznajemy ten właśnie wierzchołek. Opiszemy, jak wyprodukować analogiczną strukturę po dołożeniu wierzchołka \(v_{q+1}\), to znaczy strukturę dla turnieju \(T_{q+1}\). Wyznaczymy takie struktury danych dla turniejów kolejno \(T_1\), \(\ldots\), \(T_n\), gdzie \(T_1\) jest pojedynczym wierzchołkiem, a \(T_n\) całym interesującym nas turniejem, co na mocy poprzedniej sekcji wystarczy nam do rozwiązania zadania.

Niech zatem \(S_1, \ldots, S_k\) będą silnie spójnymi składowymi turnieju \(T_q\) w porządku topologicznym. Niech \(b\) będzie najmniejszą taką liczbą, że istnieje krawędź od wierzchołka \(v_{q+1}\) do któregokolwiek wierzchołka z \(S_b\) (lub \(k+1\) jeżeli żadna taka krawędź nie istnieje). Niech również \(e\) będzie największą taką liczbą, że istnieje krawędź od któregokolwiek wierzchołka z \(S_e\) do \(v_{q+1}\) (lub \(0\) jeżeli żadna taka krawędź nie istnieje).

Łatwo zauważyć, że zachodzi \(b \le e + 1\), gdyż w przeciwnym przypadku otrzymalibyśmy, że ani żadna krawędź ze składowej \(S_{e+1}\) nie może wchodzić do \(v_{q+1}\) (gdyż \(e+1>e\)) ani z \(v_{q+1}\) żadna krawędź nie może wchodzić do \(S_{e+1}\) (gdyż \(e+1<b\)).

Jeżeli \(b=e+1\), to wtedy od wszystkich wierzchołków ze składowych \(S_{\le e}\) krawędzie wchodzą do \(v_{q+1}\), a z \(v_{q+1}\) wychodzą krawędzie do wszystkich wierzchołków ze składowych \(S_{\ge b}\), zatem \(v_{q+1}\) staje się sam jednowierzchołkową spójną składową, która w porządku topologicznym jest wciśnięta pomiędzy \(S_e\) oraz \(S_{e+1}\).

Jeżeli \(b \le e\), to wtedy możemy zauważyć, że składowe \(S_b, S_{b+1}, \ldots, S_e\) (wraz z \(v_{q+1}\)) scalają się do jednej silnie spójnej składowej. Jest tak, gdyż z \(S_e\) można dojść do \(v_{q+1}\), z \(v_{q+1}\) do \(S_b\), a z \(S_b\) do \(S_e\), odwiedzając po drodze wszystkie pośrednie silnie spójne składowe.

Ponadto, jeżeli znamy cykle Hamiltona w \(S_b, \ldots, S_e\), to możemy wyznaczyć cykl Hamiltona w nowej składowej powstałej z \(S_b, \ldots, S_e, v_{q+1}\). W tym celu rozważymy dwa przypadki: gdy \(b < e\) oraz gdy \(b = e\).

Jeżeli \(b < e\), to cykl Hamiltona z każdej ze składowych \(S_b, \ldots, S_e\) możemy „rozciąć" w dowolnym miejscu, a następnie skleić je w jeden. Kolejność jest następująca: rozcięty cykl z \(S_b\), rozcięty cykl z \(S_{b+1}\), \(\ldots\), i na końcu \(v_{q+1}\). Pamiętajmy, że cykl z \(S_b\) musimy rozciąć w takim miejscu, aby jego pierwszy wierzchołek był taki, że wchodzi do niego krawędź z \(v_{q+1}\). Natomiast cykl z \(S_e\) musimy rozciąć w takim miejscu, aby jego ostatni wierzchołek był taki, że wychodzi z niego krawędź do \(v_{q+1}\). Jeżeli \(b \neq e\), to oba te wymagania możemy spełnić w trywialny sposób i uzyskać żądany cykl Hamiltona dla całej wynikowej składowej.

Jeżeli \(b=e\), wtedy na cyklu istnieją takie dwa kolejne wierzchołki, że z pierwszego z nich prowadzi krawędź do \(v_{q+1}\), zaś z \(v_{q+1}\) prowadzi krawędź do drugiego. Przejdźmy do formalnego dowodu.

Niech \(C\) będzie tym cyklem, \(v_{in} \in C\) takim wierzchołkiem, że istnieje krawędź z \(v_{q+1}\) do \(v_{in}\), a \(v_{out}\) takim wierzchołkiem, że istnieje krawędź z \(v_{out}\) do \(v_{q+1}\). Wiemy, że takie wierzchołki \(v_{in}\) oraz \(v_{out}\) istnieją z definicji liczb \(b\) oraz \(e\).

Niech \(succ\) będzie funkcją, która dla wierzchołka z \(C\) zwraca jego następnika na tym cyklu. Niech \(go(a, b)\) będzie predykatem, który jest prawdziwy wtedy i tylko wtedy, gdy istnieje krawędź z wierzchołka \(a\) do \(b\) (wiemy, że dla każdej pary różnych wierzchołków \(a, b\) zachodzi dokładnie jedno z \(go(a, b)\) oraz \(go(b, a)\)). Chcemy udowodnić, że istnieje taki wierzchołek \(u \in C\), że \(go(u, v_{q+1})\) oraz \(go(v_{q+1}, succ(u))\) — wtedy jesteśmy w stanie uzyskać nowy cykl Hamiltona, w którym następnikiem \(u\) staje się \(v_{q+1}\), a następnikiem \(v_{q+1}\) staje się \(succ(u)\). Na razie wiemy jednak tylko tyle, że istnieją takie \(v_{in}, v_{out} \in C\), że \(go(v_{out}, v_{q+1})\) oraz \(go(v_{q+1}, v_{in})\). Załóżmy wbrew tezie, że dla każdego wierzchołka \(u \in C\), jeżeli \(go(u, v_{q+1})\), to także \(go(succ(u), v_{q+1})\). Stąd, istnieje takie \(a\), że \(go(a, v_{q+1})\), co w istocie jest zaprzeczeniem tezy. Jednak dostajemy wtedy, że skoro \(go(v_{out}, v_{q+1})\), to także \(go(succ(v_{out}), v_{q+1})\), ale wtedy także \(go(succ(succ(v_{out})), v_{q+1})\), itd. W konsekwencji otrzymujemy, że dla każdego wierzchołka \(u \in C\) zachodzi \(go(u, v_{q+1})\), ale jest to nieprawdą na mocy założenia, że istnieje \(v_{in}\) taki, że \(go(v_{q+1}, v_{in})\). Uzyskana sprzeczność pokazuje, że jesteśmy w stanie znaleźć cykl Hamiltona dla składowej \(S_b\) poszerzonej o \(v_{q+1}\).

Opisany algorytm działa w złożoności czasowej \(O(n^2)\).

Jako dodatkowe zadanie na przećwiczenie pozyskanej wiedzy proponujemy zadanie „Tournament" z platformy Codeforces.