Omówienie zadania Drogi rowerowe (II etap XXV OI)

Już po przeczytaniu pierwszego akapitu tego zadania widać, że będziemy mieli do czynienia z zadaniem grafowym, ponieważ mamy tutaj sieć dróg rowerowych łączących skrzyżowania. Sieć ta składa się z odcinków dróg, które będziemy reprezentować za pomocą krawędzi i łączą one skrzyżowania, które będziemy reprezentować za pomocą wierzchołków grafu. Odcinki dróg są jednokierunkowe, tak więc graf będzie skierowany. I tutaj definiujemy również, co rozumiemy przez drogą pomiędzy dwoma skrzyżowaniami. Jest to po prostu ciąg krawędzi poprawnie skierowanych, przechodzących przez parami różne wierzchołki.

Dalej w treści zadania opisana jest pewna właściwość naszej sieci, nazwana tutaj sprawiedliwością. I brzmi ona tak: jeśli z jakiegoś skrzyżowania nie da się dojechać do jakiegoś innego skrzyżowania, to z tego drugiego skrzyżowania może istnieć co najwyżej jedna droga do skrzyżowania pierwszego. Do tej właściwości za chwilę sobie wrócimy. Natomiast naszym zadaniem będzie obliczenie stopnia przejezdności sieci, czyli dla każdego skrzyżowania będziemy chcieli poznać liczbę skrzyżowań, do których można z tego skrzyżowania dojechać, oczywiście respektując jednokierunkowość odcinków dróg.

Przeanalizujmy na początek test przykładowy. Jeżeli wybierzemy wierzchołek \(1\), to dojedziemy z niego do wierzchołków \(4\) i \(6\), a z nich do wierzchołka \(2\), przy czym liczymy go tylko jeden raz. Więc z wierzchołka 1 jesteśmy w stanie dojechać do trzech wierzchołków.

Podobnie z wierzchołka \(2\): możemy pojechać do wierzchołka \(1\), wobec tego również tutaj wierzchołki \(1\), \(4\), \(6\) będą osiągalne, więc odpowiedź również jest 3. Z kolei z wierzchołka \(3\) możemy jedynie dojechać do wierzchołka \(7\) i odpowiedź jest równa 1.

Podział na silnie spójne składowe

Dosyć często, gdy mamy zadanie, w którym dany jest graf skierowany, opłaca się zadać sobie pytanie, czy zadanie uprości się, jeżeli rozważymy podział tego grafu skierowanego na silnie spójne składowe. Przypomnijmy, że silnie spójna składowa to taki maksymalny zbiór wierzchołków grafu, że z każdego wierzchołka z tego zbioru możemy dojechać krawędziami do dowolnego innego wierzchołka z tego zbioru.

Popatrzmy, jakie mamy silnie spójne składowe w przykładzie. Zauważmy, że z wierzchołka \(1\) jesteśmy w stanie dojechać do wierzchołków \(4\), \(2\), \(6\) i również z wierzchołków \(4\), \(2\) i \(6\) jesteśmy w stanie wrócić przez wierzchołek \(2\) do wierzchołka \(1\). Wynika z tego, że tak naprawdę z każdego wierzchołka jesteśmy w stanie dojechać do każdego innego i te cztery wierzchołki tworzą jedną silnie spójną składową.

Pozostałe wierzchołki będą już tworzyły osobne silnie spójne składowe, czyli mamy jednowierzchołkowe składowe dla wierzchołków \(5\), \(3\) i \(7\).

Wierzchołki, które należą do jednej silnie spójnej składowej, często współdzielą podobne właściwości. W szczególności wszystkie wierzchołki z czterowierzchołkowej spójnej składowej mają odpowiedź, czyli liczbę wierzchołków osiągalnych z nich równą 3. Z kolei w jednowierzchołkowych składowych odpowiedzi są różne.

Nie jest to przypadek. Jeżeli mamy silnie spójną składową, z której nie wychodzą krawędzie do innych składowych, to zauważmy, że ponieważ z każdego wierzchołka możemy odwiedzić wszystkie inne, to znaczy, że odpowiedź w każdym wierzchołku to musi być rozmiar składowej minus 1.

Z kolei gdybyśmy mieli bardziej skomplikowany przykład, w którym z tej składowej wychodziłyby jeszcze jakieś inne krawędzie, więc potencjalnie byłoby więcej wierzchołków, które byłyby osiągalne. Tak więc w takim przypadku osiągamy wszystkie wierzchołki w środku składowej oraz wszystkie wierzchołki, które są osiągalne krawędziami wychodzącymi z tej silnej spójnej składowej, przy czym nie jest istotne, skąd one z tej silnej spójnej składowej wychodzą. Tak więc tak naprawdę dla silnej spójnej składowej nie jest istotne, jak wyglądają połączenia między wierzchołkami wewnątrz niej. Istotny jest tylko rozmiar tej składowej oraz istotne są połączenia tej składowej z innymi.

Wobec tego możemy zastąpić nasz graf grafem silnie spójnych składowych, w którym dla każdej spójnej składowej będziemy mieli dokładnie jeden wierzchołek i będziemy mieli krawędzie, które łączą różne silnie spójne składowe. Dodatkowo dla każdej składowej będziemy pamiętali, jaki jest rozmiar tej składowej, czyli ile miała w środku wierzchołków.

Programowanie dynamiczne na DAG-u

Taką przyjemną właściwością grafu silnie spójnych składowych jest to, że jest on acykliczny, czyli jest DAG-iem. To znaczy, że możemy posortować wierzchołki tego grafu topologicznie, to znaczy znaleźć taką kolejność tych wierzchołków, że każda krawędź będzie prowadzić z wierzchołka o mniejszym numerze do wierzchołka o większym numerze.

Dzięki takiej kolejności, w niektórych zadaniach jesteśmy w stanie zaproponować rozwiązanie korzystające z programowania dynamicznego, w którym przeglądamy właśnie wierzchołki w odwróconym porządku topologicznym. Przykładowo, gdyby nasze zadanie polegało na tym, że chcielibyśmy obliczyć najdłuższą ścieżkę w DAG-u, to taka najdłuższa ścieżka, oznaczmy ją \(m[v]\) dla pewnego wierzchołka \(v\), wyglądałaby następująco. Patrzymy sobie na wierzchołek \(v\), z którego wychodzą jakieś krawędzie do pewnych wierzchołków od \(u_1\) do \(u_s\). Zauważmy, że jeżeli chcemy policzyć długość najdłuższej ścieżki w wierzchołku \(v\), no to wiemy, że musimy jakąś krawędzią z tego wierzchołka wyjść, a następnie musimy kontynuować najdłuższą ścieżkę z któregoś wierzchołka \(u_i\). Więc jeżeli dla wierzchołków od \(u_1\) do \(u_s\) już obliczyliśmy długości najdłuższych ścieżek \(m[u_1], \ldots, m[u_s]\), no to dla wierzchołka \(v\) mamy \[m[v] = 1 + \max_i m[u_i].\]

Czy podobnej metody nie moglibyśmy zastosować w naszym zadaniu, czyli chcielibyśmy napisać taki wzór rekurencyjny na liczbę wierzchołków \(d[v]\) osiągalnych z wierzchołka \(v\), przy czym pamiętajmy, że \(v\) reprezentuje pewną silnie spójną składową. Wobec tego ta liczba \(d[v]\) to będzie rozmiar tej składowej \(v\) plus suma po wszystkich \(d[u_i]\): \[d[v] = rozmiar[v] + \sum_i d[u_i].\] Tutaj uwaga jest taka, że wygodniej nam będzie założyć, że wierzchołek, z którego startujemy, również jest osiągalny sam z siebie, zatem do wzoru bierzemy rozmiar składowej, a nie rozmiar minus 1. Z kolei, gdy będziemy wypisywać odpowiedź, po prostu będziemy musieli pamiętać, żeby odjąć od niej 1.

Analiza algorytmu

To rozwiązanie zadziałałoby tutaj na przykładzie, niestety w ogólności jest błędne. Żeby się o tym przekonać, dodajmy dwa wierzchołki 8 i 9 do przykładowego grafu i trzy krawędzie \(4 \to 8\), \(8 \to 9\) oraz \(2 \to 9\). Nasz algorytm wyznaczy następujące wartości dla składowych: \[d[\{9\}] = 1, \qquad d[\{8\}] = 2, \qquad d[\{1,2,4,6\}] = 7.\] Niestety ostatnia z tych liczb jest błędna, bo osiągalnych wierzchołków z 1 jest 6, a nie 7. Problem leży w tym, że te wierzchołek ze składowej \(\{9\}\) został policzony dwukrotnie: raz, gdy bezpośrednio jechaliśmy do niego krawędzią \(2 \to 9\), a drugi raz, gdy jechaliśmy pośrednio \(4 \to 8 \to 9\) przez tą silnie spójną składową \(\{8\}\).

Co więcej, nie jest znany istotnie szybszy algorytm, który rozwiązywałby to zadanie, to znaczy dla każdego wierzchołka sprawdzał w DAG-u, ile wierzchołków jest z niego osiągalnych, szybciej niż w czasie kwadratowym od liczby wierzchołków w grafie, co jest dla nas zbyt wolno, patrząc na to, że liczba wierzchołków w grafie może być rzędu \(50\,000\).

Jak sobie z tym poradzić? Kluczowe będzie przypomnienie sobie, że ten graf ma pewną specjalną własność: jest sprawiedliwy, czyli jeżeli z pewnego skrzyżowania nie da się dojechać do innego skrzyżowania, to droga powrotna może istnieć co najwyżej jedna.

Początkowo ta własność może wydawać się dosyć dziwna, ale gdy przyjrzymy się jej bliżej, to okaże się, że w naszym zadaniu będzie ona kluczowa. W szczególności przykład, w którym mieliśmy trudność z rozwiązaniem, nie spełnia tej własności, to znaczy nie jest sprawiedliwy.

Wynika to z tego, że ze składowej \(\{9\}\) nie mamy żadnej drogi do składowej \(\{1,2,4,6\}\), czyli nie ma żadnej drogi z \(u=9\) do \(v=1\). Tak więc, gdyby graf miałby być sprawiedliwy, to mogłaby istnieć co najwyżej jedna droga z \(v\) do \(u\), a istnieją dwie: \(1\to 2 \to 9\) oraz \(1 \to 4 \to 8 \to 9\).

Okazuje się, że w ogólności ta własność powoduje, że nasz algorytm będzie działał prawidłowo. To znaczy, że możemy niezależnie zsumować wkłady z wierzchołków osiągalnych dla wierzchołków \(u_1\) do \(u_s\), ponieważ nie będzie istniała sytuacja, że z jakichś dwóch wierzchołków osiągniemy ten sam jakiś wierzchołek dalej, czyli że zostanie on policzony więcej niż raz.

Załóżmy bowiem, że taki wierzchołek \(u\) będziemy mogli osiągnąć, na przykład z \(u_1\) i z \(u_2\). Ale ponieważ wiemy, że nie istnieje droga z wierzchołka \(u\) do \(v\), to znaczy, że z wierzchołka \(v\) do \(u\) powinna istnieć tylko jedna droga. No a w tym wypadku widzimy, że istnieje droga zarówno przez \(u_1\), jak i przez \(u_2\).

Tak więc podsumowując, własność sprawiedliwości powoduje, że ten dosyć taki standardowy algorytm na programowanie dynamiczne w zadaniu zadziała. Podsumujmy złożoność czasową algorytmu. Zarówno obliczenie silnie spójnych składowych, jak i stworzenie grafu spójnych składowych, a następnie posortowanie go topologicznie, to są standardowe algorytmy działające w czasie liniowym od wielkości grafu. Również nasze programowanie dynamiczne jest to jedna prosta pętla, która działa w czasie liniowym.