Drogi - Potyczki Algorytmiczne 2005

Drogi – Potyczki Algorytmiczne 2005(Finał)

W zadaniu “Drogi” musimy pomóc królowi Bajtazarowi w obliczeniu ile minimalnie dróg jednokierunkowych trzeba dobudować, aby dało się dojechać z każdego miasta do każdego innego.

Polecenie dość prosto można przekształcić na język grafów. Należy dodać minimalną liczbę krawędzi skierowanych do grafu wejściowego, tak by powstały graf był silnie spójny. W omówienie, tak samo jak w treści, zostało przyjęte, że n to liczba wierzchołków, m to liczba krawędzi.

Rozwiązanie brutalne

Po przeczytaniu zadania pierwszym co się nasunie, może być przeglądanie wszystkich wierzchołków w grafie i dla każdego z ich dzieci sprawdzenie czy da się w jakikolwiek sposób wrócić do rodzica. dro - test przykładowy

Dla pokazanego wyżej testu nasz połączy miasta: “6 i 1” oraz “4 i 3“, gdyż z “6 nie da się wrócić do 1“, podobnie jak z “4 do 3“, i zwróci wynik 2.

Rozwiązanie zmusza nas jednak do przeszukania grafu dla każdej krawędzi, bo:

  • przeglądając wszystkich sąsiadów każdego wierzchołka “przejdziemy” każdą krawędzią;
  • dla każdego sąsiada musimy przeszukać być może nawet cały graf, aby dowiedzieć się czy da się wrócić do miasta, z którego przyszliśmy;

Przez to całość działa w pesymistycznym czasie O(m*(n+m)), co jest stanowczo za wolne dla ograniczenia m = 105.


Rozwiązanie wzorcowe

 

Implementacja tego rozwiązanie znajduje się na moim GitHubie.

 

W poprzednim rozwiązaniu nie skorzystaliśmy z tego co nasuwa problem: Silnie Spójnych Składowych(w silnie spójnej składowej da się dość z każdego wierzchołka do każdego innego). W naszym zadaniu musimy doprowadzić do sytuacji, w której cały graf jest jedną silnie spójna składową. Na początku wyznaczmy więc SSS’y naszego wejściowego grafu:

  • obliczamy czasy przetworzenia wierzchołków w kolejności post-order algorytmem przeszukiwania w głąb (DFS).
  • wywołujemy algorytm DFS dla grafu transponowanego(odwrotnego) w kolejności malejących czasów przetworzenia wierzchołków. Wszystkie wierzchołki w jednym drzewie przeszukiwania w głąb należą do jednej silnie spójnej składowej.

W mojej implementacji zajmuję się tym funkcja “computeSSS()” .

Znając numer SSS, do której należy każdy z wierzchołków, możemy teraz zbudować 2 grafy, których wierzchołkami, będą SSS’y, a krawędziami połączenia jednokierunkowe pomiędzy składowymi, z tym że w 2 grafie dodajemy krawędzie odwrotne (dlaczego? – o tym za chwile 😉 ). Następnie tworzymy 2 zmienne odpowiadające za wynik w danym grafie oraz przeglądamy wierzchołki w grafie. Jeśli któryś z nich nie ma krawędzi wychodzących zwiększamy jego wynik o 1. Naszym wynikiem wyjściowym będzie większa z tych 2 liczb.

Magia – czyż nie? 😀

 

Dlaczego zliczamy “puste” wierzchołki?

Zauważmy, że najbardziej optymalne będzie wykorzystanie istniejących krawędzi i dobudowywanie nowych tylko, gdy już normalnie nie możemy iść dalej. Oczywiście ostatnie “końcówki” trzeba podpiąć do początku by powstał cykl.

 

Przykład3Dla danego przykładu musimy zwrócić 2, gdyż mam 2 końce i każdy z nich musi mieć krawędź do początku.

 

 

 

 

Dlaczego potrzebujemy 2 graf(odwrócony)?

Może zdarzyć się sytuacja, gdy początkowych wierzchołków będzie więcej niż końcowych, a my zliczymy po 1 krawędzie od końcowej(to może nie wystarczyć).

 

przykład2W tym przykładzie wynik dla pierwszego grafu  wynosi 1, gdyż jest tylko 1 koniec(nr 3), a poprawna odpowiedź to 2. Taką odpowiedź zwróci odwrócony graf, dla którego końcami będą początki normalnego.

 

 

 

Jak łatwo się domyśleć nie będzie więcej przypadków, gdyż mamy, albo więcej zakończeń, albo więcej początków(dla równości wyniki będą równe).

 

Podsumowanie

 

Zadanie nie było bardzo trudne, ale wymagało dogłębnej analizy. Bardzo łatwo było też przeoczyć sytuację nr 2, przez co traciliśmy około 40pkt.

Mam nadzieję, że omówienie było zrozumiałe. Zachęcam do napisania opinii lub wszelakich pytań w sekcji komentarzy 🙂

 

1 thought on “Drogi – Potyczki Algorytmiczne 2005(Finał)

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *