Zad4 - Najkrótsza Droga w Serwisie Społecznościowym

(Tym razem historyjka tylko dla chętnych)

Mamy serwisy społecznościowe, a w nich opcję "najkrótsza droga" pokazujące jaka jest najkrótsza "droga" po naszych znajomych i ich znajomych etc. do osoby nam nie znanej. Może być to przydatne do wielu celów: kiedy chcemy wypytać "co to za osoba" przed zatrudnieniem jej, poprosić, żeby ktoś nas z nią poznał albo w tym pomógł (np. w celach "towarzyskich").

Zwykle te serwisy mają ograniczenie, iż podają tylko pierwsza znalezioną drogę.

Jasio chce poznać Małgosię, znalazł jej profil w serwisie społecznościowym, ale droga którą serwis pokazuje prowadzi przez konkurenta Jasia.

Pomóż Jasiowi zdobyć serce Małgosi znajdując wszystkie najkrótsze drogi prowadzące do Małgosi przez każdego z jej znajomych.

Zakładamy że już udało ci się scrawlować potrzebny fragment sieci społecznej, oraz sparsować i przekonwerować na postać czystego grafu, gdzie osoby są zmapowane na wierzchołki 0..n-1, a krawędzie reprezentują połączenia z sieci społecznej.

(Dla żądnych większych emocji historyjka alternatywna: chcemy wykraść świetnego pracownika konkurencji, w tym celu szukamy jak najskuteczniej dojść do niego po jego znajomych… albo coś z CIA itp.)

Dla danego grafu nieskierowanego nieważonego G i pary wierzchołków start, dest ; dla każdego wierzchołka f połączonego bezpośrednio z dest znajdź wszystkie najkrótsze drogi od start do dest prowadzące przez ten wierzchołek f.

Znalezione ścieżki mają być acykliczne (każdy wierzchołek na ścieżce znajduje się tylko raz).

W pierwszym wierszu oddzielone pojedynczymi spacjami: n m start dest.

Wierzchołki numerowane: 0..n-1.

W kolejnych m liniach pary u, v oznaczające krawędź między u, a v.

Znalezione ścieżki, wypisane po jednej w każdym wierszu zgodnie z następującym formatem:

l v1 v2 … vl - pierwsza liczba l to ilość węzłów na ścieżce, potem wypisane l kolejnych wierzchołków na ścieżce poczynając od startowego start a kończąc na docelowym dest.

Liczby całkowite, oddzielone pojedynczą spacją.

Kolejność wierszy dowolna, ale koniecznie liczby całkowite oddzielone pojedynczą spacją, bez białych znaków na początku wiersza, ponieważ wyniki będą porządkowane unix-owym poleceniem sort -u.

Pesymistyczna złożoność obliczeniowa : O(n+m+k) ; gdzie k to sumaryczna długość znalezionych ścieżek.

Pamięciowa: O(n+m)

Limit pamięci: około 400MB.