Wycieczki

Kontynuując wątek ACM ICPC 2015, proponuję krótką dyskusję na temat ślicznego zadania K. Co prawda wszyscy zainteresowani pewnie umieją je już rozwiązać, ale być może nie w czasie liniowym.

Treść można znaleźć tutaj. Dostajemy graf nieskierowany, którego krawędzie chcielibyśmy pomalować na k kolorów tak, aby każdy cykl prosty był zbalansowany kolorystycznie. Przez takie zbalansowanie kolorystyczne rozumiemy, że liczba krawędzi każdego koloru jest taka sama (przy czym być może różna dla różnych cykli!). Należy podać wszystkie liczby k, dla których da się w żądany sposób pomalować wszystkie krawędzie. Autor (czy też autorzy) gwarantują, że w grafie istnieje przynajmniej jeden cykl prosty, a sam graf nie posiada pętli ani krawędzi wielokrotnych. Oraz że n,n\leq 2000, czyli pewnie celujemy w rozwiązanie o złożoności kwadratowej.

Kuszące wydaje się popatrzenie na wszystkie możliwe długości cyklów prostych. Oczywiste jest bowiem, że k musi dzielić każdą taką długość (skoro na każdym cyklu prostym mamy tyle samo krawędzi każdego koloru). Musi więc także dzielić ich największy wspólny dzielnik. Taki największy wspólny dzielnik pewnie nawet potrafilibyśmy dość szybko policzyć, ale niestety nie prowadzi to jeszcze do prawidłowego rozwiązania.

Kluczowe w prawidłowym rozwiązaniu jest zdefiniowanie relacji równoważności na krawędziach. Mówimy, że krawędzie e oraz e' są równoważne, jeśli każdy cykl prosty zawierający jedną z nich musi zawierać także tą drugą. Piszemy wtedy, że e \equiv e'. Na przykład jeśli nasz graf to po prostu jeden wielki cykl, mamy tylko jedną klasę równoważności, do której należą wszystkie krawędzie. Nie jest dla mnie do końca jasne jak można wpaść na to, że taka definicja pomaga w zbliżeniu się do rozwiązania, ale jak widać na ostatecznym rankingu kilka drużyn nie miało większych problemów z poczynieniem takiej obserwacji. Zanim zastanowimy się jednak nad jej przydatnością, sprawdźmy, że rzeczywiście jest to relacja równoważności.

Lemat 1. Jeśli e\equiv e' ora e' \equiv e'' to e\equiv e''.

Dowód. Weźmy dowolny cykl prosty zawierający e. Z założenia musi zawierać on także e'. Ale wiemy także, że każdy cykl prosty zawierający e' musi zawierać również e'', czyli nasz cykl tak naprawdę zawiera także e''. Czyli e\equiv e''.

OK, ale dlaczego taka relacja równoważności może pomóc w rozwiązaniu zadania? Otóż okazuje się, że wszystkie krawędzie należące do tej samej klasy równoważoności muszą być zbalansowane kolorystycznie (jest to istotnie silniejszy warunek niż ten wspomniany na samym początku). Żeby się o tym przekonać, wyobraźmy sobie taką klasę równoważności.

wycieczki1

Powyższy rysunek wcale nie jest tendencyjny: każda klasa równoważności to „naszyjnik” złożony z dwuspójnych składowych połączonych krawędziami tworzącymi klasę równoważności. Przez dwuspójną składową rozumiemy tutaj podgraf, w którym między każdą parą wierzchołków istnieją dwie rozłączne krawędziowo ścieżki (czyli nie ma mostów; mostem nazywamy krawędź, której usunięcie rozspaja graf). Pewnie wymaga to jakiegoś uzasadnienia: weźmy więc jedną z krawędzi należących do danej klasy i usuńmy ją z grafu. Z definicji, pozostałe krawędzie w tej klasie to dokładnie mosty w otrzymanym grafie. Ale to oznacza, że leżą one na ścieżce między dwoma dwuspójnymi składowymi w drzewie dwuspójnych składowych (takie drzewo powstaje przez zkolapsowanie każdej dwuspójnej składowej do jednego wierzchołka; łatwo sprawdzić, że w tak skonstruowanym grafie nie ma cykli). Ta ścieżka plus usunięta krawędź dają nam szukany naszyjnik. Widać, że każde dwie krawędzie na naszyjniku są w tej samej klasie równoważności oraz że nie ma w tej klasie żadnych innych krawędzi.

Skoro wiemy już, jak wygląda klasa równoważności, możemy zabrać się za uzasadnienie tego, że jej krawędzie koniecznie muszą być zbalansowane kolorystycznie. Oznaczmy końce i-tej krawędzi przez (u_i,v_i). Z definicji dwuspójnej składowej istnieją dwie rozłączne ścieżki (proste) między v_i a u_{i+1}. Utwórzmy dwa cykle proste wybierając odpowiednio pierwszą lub drugą z tych dwóch ścieżek w każdej dwuspójnej składowej i łącząc je krawędziami (u_i,v_i) tak jak na poniższej ilustracji.

wycieczki2

Czyli otrzymaliśmy dwa duże cykle proste. Dodatkowo w każdej dwuspójnej składowej mamy też mały cykl prosty złożony z dwóch ścieżek łączących v_i oraz u_{i+1}. Wiemy, że wszystkie te cykle muszą być zbalansowane kolorystycznie, czyli różnica liczby krawędzi czerwonych i liczby krawędzi zielonych jest równa zeru (kolory czerwony i zielony można zastąpić swoimi ulubionymi). Ale to oznacza, że dodając do siebie obydwa duże cykle i następnie odejmując wszystkie małe, otrzymamy zbalansowany kolorystycznie podgraf składający się z dwóch kopii każdej krawędzi (u_i,v_i). Czyli dwukrotność różnicy liczby krawędzi czerwonych i liczby krawędzi zielonych w danej klasie równoważności jest równa zeru. Ale to przecież oznacza, że te liczby są sobie równe, czyli faktycznie cała klasa jest zbalansowana kolorystycznie.

Świetnie, czyli rzeczywiście dostaliśmy sensowny warunek konieczny: k musi dzielić największy wspólny dzielnik liczności wszystkich klas równoważności. Okazuje się on być także warunkiem wystarczającym, i to z dość prostego powodu. Otóż dowolny cykl prosty jest sumą pewnych klas równoważności (całych: z definicji klasy równoważności żaden cykl prosty nie może przechodzić tylko przez niektóre z jego krawędzi). Skoro każda klasa jest zbalansowana kolorystycznie, zbalansowana kolorystycznie jest także ich suma, czyli cykl.

Czyli udało nam się znaleźć konieczny i wystarczający warunek na poprawne liczby k. Wystarczy tylko znaleźć wszystkie klasy równoważności, a następnie policzyć największy wspólny dzielnik ich liczności. To drugie jest proste, ale jak szybko rozbić krawędzie na klasy równoważności? Najprościej pewnie wybierając dowolną krawędź e, usuwając ją z grafu, i znajdując mosty. Daje nam to całą klasę równoważności, do której należy e, w czasie \mathcal{O}(n+m). Powtarzając rozumowanie dla każdej krawędzi, dostajmy rozwiązanie całego zadania, które działa w czasie \mathcal{O}((n+m)^2), co dość dobrze pasuje do limitów z treści. Nietrudno zmodyfikować je tak, aby działało w czasie \mathcal{O}(m+n^2), ale skoro zadanie jest z teorii grafów, może dałoby się liniowo?

Całe zadanie wydaje się dość blisko związane ze sprawdzaniem trójspójności grafu. Jeśli bowiem każda klasa równoważności składa się z tylko jednej krawędzi (oraz nie ma żadnych mostów, a graf jest spójny), do rozspójnienia potrzebne jest usunięcie przynajmniej trzech krawędzi. Co wiadomo o sprawdzaniu trójspójności? Szybkie zapytanie do Google mówi nam, że całkiem sporo. W szczególności od dawna wiadomo jak podzielić graf na trójspójne składowe w czasie liniowym (darujmy sobie na razie definiowanie trójspójnych składowych). Ta praca posiada jednak przynajmniej dwie fundamentalne wady: ma 62 strony oraz zajmuje się spójnością wierzchołkową, podczas gdy nas interesuje spójność krawędziowa. To drugie daje minimalną nadzieję, że może da się jakoś prościej. Spróbujmy.

Zacznijmy od przypomnienia sobie, jak szuka się mostów. Przeszukujemy graf w głąb dzieląc krawędzie na drzewowe (czyli te, które prowadzą od ojca do dziecka w drzewie) oraz w tył (które prowadzą od wierzchołka do jednego z jego przodków w drzewie przeszukiwania). Teraz dla każdego wierzchołka v rozważamy jego poddrzewo T_v i krawędzie, które z niego wystają. Są to te krawędzie w tył, których jeden koniec znajduje się w T_v, a drugi jest (właściwym) przodkiem v, tak jak na poniższej ilustracji.

wycieczki3

Tylko krawędzie drzewowe mogą być mostami. Łatwo też sprawdzić, że krawędź z u do v w drzewie jest mostem dokładnie wtedy, gdy z T_v nie wystają żadne krawędzie. Ten warunek zwykle sprawdza się wyznaczając dla każdego v najmniejszy (w porządku preorder) wierzchołek, do którego można dotrzeć z T_v idąc dokładnie jedną krawędzią w tył. Jeśli ten najmniejszy wierzchołek jest właściwym przodkiem v, to krawędź (u,v) jest mostem. Wszystkie takie najmniejsze wierzchołki łatwo wyznaczyć podczas przeglądania grafu w głąb.

Wyobraźmy sobie parę krawędzi e\equiv e'. Naszym celem jest podania efektywnej (algorytmicznie) charakteryzacji wszystkich takich par krawędzi. Usunięcie e oraz e' rozspaja graf (z definicji relacji równoważności), więc przynajmniej jedna z tych krawędzi musi być krawędzią drzewową. Naturalne jest więc rozważanie osobno dwóch przypadków.

Załóżmy, że e=(u,v) jest krawędzią drzewową, a e' krawędzią w tył. Widać, że e' musi wystawać z T_v (zakładamy, że u jest ojcem v). Tak naprawdę e' musi być jedyną krawędzią wystającą z T_v, bo przecież w przeciwnym wypadku usunięcie e i e' nie rozspajałoby grafu! Dla każdego v chcielibyśmy więc szybko sprawdzić, czy T_v wystaje dokładnie jedna krawędź, no i sprawnie się do niej dobrać. W tym celu wystarczy tylko lekko uogólnić wspomniany przed chwilą algorytm wyznaczający mosty. Zamiast wyliczać dla każdego v najmniejszy wierzchołek, do którego można dotrzeć z T_v idąc dokładnie jedną krawędzią w tył, możemy w takim samym czasie wyznaczyć dwa najmniejsze wierzchołki o takiej własności (uwaga: być może do najmniejszego wierzchołka można dotrzeć dwoma różnymi krawędziami w tył, wtedy liczymy go podwójnie). Jeśli pierwszy z nich jest właściwym przodkiem v, a drugi leży w poddrzewie v, to krawędź e' prowadząca do tego pierwszego jest szukaną krawędzią w tył. Czyli możemy łatwo wygenerować wszystkie pary takich krawędzi w sumarycznym czasie \mathcal{O}(n+m).

Teraz możemy zabrać się za (trudniejszy) przypadek, w którym zarówno e jak i e' są krawędziami drzewowymi. Ustalmy krawędź e=(u,v) (znów, u jest ojcem v) i wyobraźmy sobie wszystkie krawędzie drzewowe e', które leżą nad e. Ponieważ koniec końców interesuje nas wyznaczenie relacji równoważności, wystarczy nam wyznaczenie najniższej z tych krawędzi, dla której e\equiv e'. Zakładamy, że e nie jest mostem, a więc istnieje chociaż jedna krawędź w tył wystająca z T_v. Ze wszystkich takich krawędzi wybieramy tę, której drugi koniec (ten, który jest właściwym przodkiem v) jest jak najniżej w drzewie, to jest jak najbliżej v. Nazwijmy tę krawędź blokującą v. Łatwo zauważyć, że wszystkie krawędzie e', dla których e\equiv e', znajdują się na ścieżce łączącej v z drugim końcem blokującej krawędzi v, czyli sytuacja wygląda jakoś tak.

wycieczki4

Teraz zauważmy, że jeśli e'=(u',v') (jak zwykle, u' jest ojcem v'), to krawędź blokująca v' musi być jednocześnie krawędzią blokującą v'. A nawet więcej: zbiory krawędzi wystających z T_v oraz T_{v'} muszą być identyczne. Po chwili zastanowienia można dojść do wniosku, że tak naprawdę jest to warunek konieczny i wystarczający, to znaczy krawędzie drzewowe e'=(u',v'), dla których e\equiv e', to dokładnie te krawędzie leżące na ścieżce łączącej v z drugim końcem blokującej krawędzi v, dla których zbiór krawędzi wystających z T_v jest taki sam jak zbiór krawędzi wystających z T_{v'}. No i fajnie, ale jak sprawdzić taki warunek?

Na pewno trzeba zacząć od wyznaczenia blokującej krawędzi dla każdego krawędzi. Załóżmy, że mamy już taką informację. Co dalej? W całym drzewie być może jest sporo wystających krawędzi i na pewno nie możemy pozwolić sobie na generowanie wszystkich zbiorów wystających krawędzi. Mamy jednak następującą przyjemną własność: skoro interesują nas tylko wierzchołki v', które leżą poniżej drugiego końca blokującej krawędzi v, to każda krawędź wystająca z T_v wystaje także z T_{v'}. A więc żeby sprawdzić, czy dwa zbiory wystających są równe, wystarczy porównać ich liczności! A policzenie liczby krawędzi wystających z każdego T_v jest już łatwe: wystarczy akumulować wynik podczas rekurencyjnego przechodzenia grafu w głąb.

Już prawie koniec. Musimy tylko wyznaczyć wszystkie blokujące krawędzie. Przypomnijmy, że dla każdego v interesuje nas dobranie się do jego najbliższego przodka u, dla którego istnieje krawędź w tył o jednym końcu w T_v a drugim w u. Spróbujmy odwrócić pytanie i dla każdego wierzchołka u wyznaczyć wszystkie v, dla których jest on tym szukanym przodkiem. Może będzie prościej?

Będzie prościej. Możemy bowiem rozważać wierzchołki u w kolejności nierosnącej głębokości w drzewie. Bierzemy kolejny u i iterujemy się po wszystkich krawędziach w tył postaci (u,u'), gdzie u jest przodkiem u'. Dla każdego v leżącego na ścieżce z u' do u w drzewie, dla którego nie wyznaczyliśmy jeszcze odpowiedzi, tą odpowiedzią jest właśnie krawędź (u,u'). Potrzebujemy więc struktury danych przechowującej (początkowo) wszystkie wierzchołki drzewa, która implementuje dwie operacje. Po pierwsze, chcemy szybko dobrać się do wszystkich aktywnych wierzchołków na danej ścieżce z wierzchołka do jego przodka w drzewie. Po drugie, chcemy deaktywować dany wierzchołek. Mając taką strukturę bez problemu wyznaczymy wszystkie blokujące krawędzie.

Zredukowaliśmy więc całe zadanie do implementacji pewnej struktury danych. Kosztowało nas to trochę pracy, ale było warto: ta struktura to bowiem nic innego jak union-find! W danym momencie każdy zbiór odpowiada pewnemu wciąż aktywnemu wierzchołkowi v oraz zawiera całą nieaktywną „czapę” T_v (czyli tych nieaktywnych potomków v, do których da się dojść z v idąc w dół po nieaktywnych wierzchołkach). Deaktywacja wierzchołka v sprowadza się do sklejenia jego zbioru ze zbiorem ojca. Wypisanie aktywnych wierzchołków na danej ścieżce to po prostu skakanie do kolejnych aktywnych wierzchołków reprezentujących zbiór danego wierzchołka i przechodzenie do ich ojców. (Po każdym takim skoku deaktywujemy jeden wierzchołek, więc nie będzie ich wiele.) Umożliwia to wyznaczenie wszystkich blokujących krawędzi w czasie \mathcal{O}(m\alpha(m,n)).

Teraz wystarczy już tylko poskładać w całość wszystkie elementy rozwiązania. Wyznaczamy wszystkie pary równowaznych krawędzi pierwszego typu, oraz niektóre pary równoważnych krawędzi drugiego typu. Następnie domykamy relację równoważności zdefiniowaną przez znalezione pary. Dzięki temu, że wsród wszystkich krawędzi drzewowych e' równoważnych e wybieramy tą najniższą, otrzymamy w ten sposób szukaną relację równoważności. Najwolniejszym elementem całej układanki jest wyznaczenie blokujących krawędzi, pozostała część rozwiązania działa w czasie \mathcal{O}(n+m).

Dobrze, ale przecież obiecałem liniówkę. Jedynym nieliniowym fragmentem powyższego rozwiązania jest union-find. Ma on jednak dość szczególną postać i można zbić złożoność obydwu operacji do zamortyzowanej stałej. Nie jestem pewien czy jest to ciekawe, w drodze wyjątku pozostańmy więc dzisiaj na prawie-liniówce.

Advertisements

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s