Omówienie zadania Rozbudowa Bajtocji (III etap XXXIII OI)

Wyobraźmy sobie \(n\) wiosek i \(m\) dróg, które dodawane są kolei - jedna droga na rok. Parada to trasa, która zaczyna się i kończy w tej samej wiosce (czyli po prostu cykl), ale nie może przejść przez żadną z dróg więcej niż raz. Naszym zadaniem jest ustalenie dla każdej drogi, w którym roku po raz pierwszy mogła stać się częścią takiej parady.

Dodatkowo, powiedziane jest, że po dodaniu wszystkich dróg graf jest spójny.

Kluczowa obserwacja: droga może być częścią parady wtedy i tylko wtedy, gdy leży na jakimś cyklu w aktualnym grafie. Innymi słowy, droga \(i\) jest „otwarta" (może być częścią parady) w roku \(t\), jeśli po usunięciu jej z grafu złożonego z dróg \(1, 2, \ldots, t\) jej końce nadal są połączone (istnieje alternatywna ścieżka).

Najprostsze rozwiązanie \(O(n^3)\)

Dla każdej drogi \(i\) i każdego roku \(t \geq i\) sprawdzamy, czy droga \(i\) jest otwarta: usuwamy ją z grafu złożonego z dróg \(1, \ldots, t\) i BFS-em sprawdzamy, czy jej końce nadal są połączone. Pierwszy taki \(t\) jest odpowiedzią. Mamy \(m\) dróg, dla każdej sprawdzamy co najwyżej \(m\) momentów w czasie, a każde sprawdzenie to BFS w czasie \(O(n + m)\). Całkowita złożoność to \(O(m^2 \cdot n)\), co przy \(m \approx n\) daje \(O(n^3)\).

Wyszukiwanie binarne \(O(n^2 \log n)\)

Zauważmy, że jeśli droga \(i\) jest otwarta w roku \(t\), to jest również otwarta w roku \(t + 1\) - dodanie kolejnej drogi nie może zlikwidować istniejącego cyklu. Oznacza to, że dla każdej drogi istnieje pewien rok \(t^*\), od którego droga staje się otwarta i pozostaje otwarta na zawsze.

Dzięki tej własności możemy dla każdej drogi \(i\) zastosować wyszukiwanie binarne po roku \(t\). Dla ustalonego \(t\) sprawdzamy, czy droga jest otwarta (tak jak poprzednio, BFS-em po usunięciu krawędzi). Daje to złożoność \(O(m \cdot \log m \cdot n)\), co przy \(m \approx n\) wynosi \(O(n^2 \log n)\).

Inne podejście - drzewo rozpinające

Wróćmy do prostszego sposobu myślenia o tym problemie. Dodajemy krawędzie po kolei i budujemy drzewo rozpinające: jeśli nowa krawędź łączy dwa dotąd niepołączone wierzchołki, dodajemy ją do drzewa (od teraz będziemy ją nazywać krawędzią podstawową), w przeciwnym razie jest to krawędź dodatkowa.

Krawędź dodatkowa \((u, v, t)\) natychmiast tworzy cykl z jedyną ścieżką z \(u\) do \(v\) w drzewie, więc jej odpowiedzią jest po prostu \(t\) (sama siebie otwiera). Dodatkowo każda krawędź podstawowa \(e\) leżąca na ścieżce w drzewie rozpinającym z \(u\) do \(v\) zostaje „pokryta" - od momentu \(t\) istnieje alternatywna droga omijająca \(e\). Odpowiedzią dla krawędzi podstawowej jest najwcześniejsza krawędź dodatkowa, która ją pokrywa.

Wystarczy więc dla każdej krawędzi dodatkowej przejść ścieżkę podstawową z \(u\) do \(v\) i zaktualizować odpowiedzi pokrytych krawędzi. Ponieważ krawędzie dodatkowe przetwarzamy w kolejności chronologicznej, pierwsza aktualizacja danej krawędzi podstawowej daje jej optymalną odpowiedź.

Przechodzenie ścieżki w drzewie rozpinającym zajmuje \(O(n)\) w najgorszym przypadku, a krawędzi dodatkowych jest \(m - n + 1\), więc złożoność wynosi \(O((m - n) \cdot n)\).

Optymalne rozwiązanie - Find & Union

Zauważmy, że w poprzednim rozwiązaniu wielokrotnie odwiedzamy krawędzie podstawowe, które już mają swoją odpowiedź. Skoro tylko pierwsza aktualizacja jest dla nas ważna, wracanie do tych krawędzi jest stratą czasu. Najlepiej byłoby je po prostu omijać.

Gdy krawędź podstawowa zostaje pokryta (otrzymuje swój rok), możemy wyobrazić sobie, że „sklejamy” jej dwa końce w jeden wierzchołek. Dzięki temu, gdy w przyszłości inna krawędź dodatkowa będzie próbowała przejść przez ten sam fragment ścieżki (idąc w górę drzewa), po prostu go przeskoczy, od razu wchodząc na kolejne, niepokryte jeszcze krawędzie. Tym sposobem każdą krawędź podstawową odwiedzimy i pokryjemy dokładnie raz.

Implementacja za pomocą Find & Union: Aby sprawnie zaimplementować to „sklejanie” wierzchołków i przeskakiwanie krawędzi, idealnie nadaje się struktura zbiorów rozłącznych (Find & Union). Łącząc wierzchołek z jego rodzicem w momencie pokrycia krawędzi, wywołanie \(\text{find}(u)\) pozwoli nam w czasie zbliżonym do stałego odnaleźć najbliższego przodka, do którego prowadzi jeszcze wolna krawędź. Całkowita złożoność tego rozwiązania spada dzięki temu do \(O((n + m) \cdot \alpha(n))\)