Omówienie zadania Osiedla (II etap XXVI OI)

Widać, że będzie to zadanie grafowe, ponieważ mamy miasto z siecią \(m\) dwukierunkowych ulic łączących \(n\) skrzyżowań. Tak więc ulice będziemy reprezentować przez krawędzie w grafie, natomiast skrzyżowania przez wierzchołki. Ponieważ ulice są dwukierunkowe, graf ten będzie nieskierowany (przy czym możliwe są w nim krawędzie wielokrotne). Burmistrz miasta chciałby zrobić z tego grafu graf skierowany, zamieniając każdą ulicę w ulicę jednokierunkową.

Czyli będziemy musieli skierować nasz graf, ale w taki sposób, żeby doprowadzić do utworzenia jak najmniejszej liczby osiedli. Osiedlem nazywamy każdy maksymalny zbiór skrzyżowań, taki że z dowolnego skrzyżowania z tego zbioru można przejechać do dowolnego innego, zgodnie ze skierowaniem ulic. Ale jest to przecież definicja silnie spójnej składowej grafu skierowanego. Tak więc nasze zadanie sprowadza się do tego, że mamy tak skierować graf, żeby uzyskać jak najmniej silnie spójnych składowych.

Gdybyśmy w teście przykładowym skierowali krawędzie \(1\to 2\), \(2\to 3\), \(3\to 1\), \(3\to 4\), \(4\to 5\), \(5\to 4\) i \(6\to 7\), to dostaniemy cztery silnie spójne składowe: \(\{1,2,3\}\), \(\{4,5\}\), \(\{6\}\) i \(\{7\}\).

Mosty

Zastanówmy się, co nam przeszkadza w tym, żeby tych silnie spójnych składowych po skierowaniu było mało. Przyjrzyjmy się krawędzi \((3, 4)\). Jeśli skierujemy ją \(3\to 4\), to z wierzchołka 4 nie będziemy mogli dostać się nigdzie na lewo, w szczególności do wierzchołka 3, dlatego, że nie istnieje żadna inna krawędź, która łączy osiedle wierzchołka 4 z osiedlem wierzchołka 3. Analogicznie, jeśli skierujemy krawędź \(4\to 3\), to z wierzchołka 3 nie osiągniemy wierzchołka 4.

Wynika to z tego, że mamy dwie części grafu, które są połączone jedynie krawędzią \((3, 4)\). Taka krawędź, której usunięcie w grafie nieskierowanym powoduje, że zwiększa się liczba spójnych składowych tego grafu, nazywa się mostem. Niemożność skierowania mostu powoduje, że spójne składowe, które most łączy, będą po skierowaniu musiały być w różnych silnie spójnych składowych grafu skierowanego. Analogiczną sytuację mamy z wierzchołkami 6 i 7, które też są połączone mostem i będą musiały znaleźć się w różnych silnie spójnych składowych.

Znajdowanie silnej orientacji

Szczęśliwie okazuje się, że mosty są jedynym problemem, który będziemy mieli przy orientacji naszego grafu. Jeżeli bowiem graf nie posiada mostów, to będziemy w stanie znaleźć taką orientację, że będziemy mieli tylko jedną silnie spójną składową. Co więcej, znaleźć taką orientację będzie bardzo prosto.

Uruchamiamy algorytm DFS z dowolnego wierzchołka w naszym grafie nieskierowanym. Za każdym razem, kiedy idziemy krawędzią drzewową (czyli do wierzchołka, który jest jeszcze nieodwiedzony), to kierujemy tę krawędź w dół drzewa (od wierzchołka wcześniej odwiedzonego do wierzchołka później odwiedzonego). Natomiast jeżeli pojawia nam się jakaś krawędź niedrzewowa (to znaczy prowadząca do wierzchołka, który już był wcześniej odwiedzony), to kierujemy ją w przeciwnym kierunku, w górę drzewa (od wierzchołka później odwiedzonego do wierzchołka odwiedzonego wcześniej).

Jeżeli graf nie będzie miał mostów, to takie skierowanie jest silnie spójne, czyli tworzy jedną silnie spójną składową. Dlaczego? Zauważmy, że z korzenia jesteśmy w stanie odwiedzić wszystkie wierzchołki w drzewie (wystarczy, że poruszamy się w dół drzewa krawędziami drzewowymi). Pytanie teraz, czy z każdego wierzchołka drzewa jesteśmy w stanie wrócić do korzenia? Załóżmy, że jesteśmy w wierzchołku \(v\) i chcemy dojść do korzenia. Jeżeli z \(v\) wychodzi krawędź niedrzewowa, to możemy pójść tą krawędzią do wierzchołka, który będzie wyżej w drzewie niż \(v\).

Co jeśli z \(v\) nie ma krawędzi niedrzewowej? To wtedy w poddrzewie zaczepionym w \(v\) będzie musiał istnieć taki wierzchołek, który będzie zawierał krawędź niedrzewową wychodzącą z tego poddrzewa. Gdyby takiej krawędzi nie było, to by oznaczało, że usunięcie krawędzi prowadzącej do ojca wierzchołka \(v\) spowodowałoby, że drzewo rozpadłoby się na dwa kawałki, zatem krawędź do ojca byłaby mostem (a założyliśmy, że graf jest bez mostów).

Zatem w każdym wierzchołku albo możemy od razu pójść krawędzią niedrzewową w górę, albo gdzieś w poddrzewie tego wierzchołka znajdziemy krawędź niedrzewową, która idzie w górę. Tak więc prędzej czy później dojdziemy do korzenia.

Tak więc jeżeli pytamy się, czy istnieje skierowana ścieżka z jakiegoś dowolnego wierzchołka \(x\) do wierzchołka \(y\), to odpowiadamy, że tak, bo wystarczy pójść z wierzchołka \(x\) do korzenia, a dalej z korzenia do wierzchołka \(y\). Wobec tego graf będzie silnie spójny.

Zadanie możemy więc rozwiązać w następujący sposób. Najpierw znajdujemy wszystkie mosty w naszym grafie nieskierowanym i usuwamy je. Teraz każda ze spójnych składowych nowego grafu nie zawiera mostów, więc będziemy mogli ją tak zorientować, żeby powstała silnie spójna składowa. (Nawiasem mówiąc, taka składowa, która nie zawiera mostów, nazywa się krawędziowo dwuspójną składową grafu.)

Na końcu możemy z powrotem dodać mosty, orientując je w dowolny sposób. Skierowanie pojedynczej składowej możemy zrobić w czasie liniowym od jej wielkości zatem sumaryczna praca będzie liniowa od sumarycznej wielkości grafu, czyli \(O(n+m)\).

Znajdowanie mostów

Pozostaje pytanie, jak znaleźć mosty. Do tego przyda nam się ponumerowanie wierzchołków w grafie w kolejności odwiedzania ich przez algorytm DFS. Niech \(t[v]\) to jest czas odwiedzenia wierzchołka \(v\).

Następnie będziemy wypełniać tabelkę \(low\). Idea jest taka, że \(low[v]\) to jest najmniejszy numer wierzchołka, do którego możemy dojść z wierzchołka \(v\), używając co najwyżej jednej krawędzi niedrzewowej.

I to możemy wyliczyć sobie jako minimum: po pierwsze z czasu odwiedzenia \(t[v]\) wierzchołka \(v\) (bo to jest przypadek, w którym nie użyjemy żadnej krawędzi), po drugie z czasów odwiedzenia \(t[x]\) dla wierzchołków \(x\), takich że krawędź z \(v\) do \(x\) jest niedrzewowa, a w końcu z wartości \(low[x]\) dla wierzchołków \(x\), takich że \(v\) od \(x\) jest krawędzią drzewową.

Te wartości łatwo z definicji obliczyć podczas przeszukiwania grafu algorytmem DFS, więc całość zajmie nam czas liniowy.

Teraz krawędź z wierzchołka \(v\) do syna \(x\) jest mostem, wtedy i tylko wtedy, kiedy \(t[x] = low[x]\), bo to oznacza, że z poddrzewa zaczepionego w \(x\) nie istnieją krawędzie niedrzewowe, które z tego poddrzewa idą gdzieś wyżej.

Tak więc ostatecznie cały algorytm ma złożoność liniową ze względu na ilość wierzchołków i krawędzi w grafie, czyli \(O(n+m)\).

Jeszcze prostszy algorytm

Okazuje się jednak, że nasze zadanie możemy rozwiązać w jeszcze prostszy sposób. Nie musimy szukać mostów, wystarczy, że w każdej spójnej składowej naszego grafu wykonamy przejście algorytmem DFS, krawędzie drzewowe kierując w dół, a krawędzi niedrzewowe kierując w górę.

Ilekroć bowiem przechodzimy mostem (kierując go w pewną stronę) do wierzchołka \(x\), to wchodzimy do nowego osiedla, w którym krawędzie będziemy kierować w ten sam sposób, w jaki byśmy je kierowali w poprzednim algorytmie, gdybyśmy te osiedle zaczęli przeglądać od wierzchołka \(x\).

To spowoduje, że dostaniemy poprawne skierowanie, które minimalizuje liczbę silnie spójnych składowych. Pozostało jednak jeszcze wypisać liczbę tych spójnych składowych, ale możemy w tak zorientowanym grafie po prostu znaleźć ich liczbę dowolnym liniowym algorytmem na znajdowanie silnie spójnych składowych. Ostatecznie złożoność czasowa również będzie \(O(n+m)\), ale cały algorytm będzie prostszy.