Marcin Sawicki	Andrzej Gąsienica--Samek
Treść zadania, Opracowanie	Program wzorcowy

Wędrowni treserzy pcheł

W Bajtocji można spotkać wędrownych treserów pcheł. Tresowane pchły uczone są tańca, polegającego na wykonywaniu precyzyjnych skoków w rytm muzyki. Dokładnie wygląda to tak: treser układa na stole w rządku ponumerowane żetony, przy czym żetony nie muszą być ułożone po kolei. Na każdym żetonie, oprócz jego numeru, jest również napisany numer żetonu, na który powinna z niego skoczyć pchła. Następnie treser ustawia po jednej pchle na każdym z żetonów i włącza muzykę. Na początku każdego taktu, każda z pcheł wykonuje skok wprost na żeton, którego numer jest napisany na żetonie, na którym w danej chwili stoi. W trakcie tańca może się zdarzyć, że kilka pcheł znajdzie się na tym samym żetonie i razem wykonują dalsze skoki.

Załóżmy, że mamy n tresowanych pcheł i n żetonów. Jeśli podamy, jakie liczby znajdują się kolejno na żetonach numer 1, 2, ..., n, to jednoznacznie opiszemy układ choreograficzny, jaki zaprezentują pchły. Jednak może się okazać, że dwa różne zestawy żetonów dają ten sam układ, jeśli tylko odpowiednio je ułożymy.

Przykład

Natomiast układy oraz są takie same - wystarczy ułożyć żetony na stole w rzędzie, w pierwszym przypadku w kolejności od lewej do prawej, a w drugim od prawej do lewej, a pchły odtańczą ten sam taniec.

Zadanie

• wczyta z pliku tekstowego pch.in liczbę przypadków testowych,
• dla każdego z przypadków wczyta z pliku pch.in opis dwóch zestawów żetonów i rozstrzygnie, czy żetony z tych zestawów można ułożyć na stole tak, by pchły wykonały taki sam taniec,
• wypisze odpowiedzi do pliku tekstowego pch.out.

Wejście

Kolejne 3d wierszy pliku pch.in opisują kolejne przypadki testowe - każdy przypadek zajmuje trzy kolejne wiersze pliku. Pierwszy z nich zawiera jedną liczbę całkowitą , równą liczbie żetonów. Każdy z dwóch następnych wierszy zawiera opis zestawu n żetonów w postaci ciągu n liczb całkowitych z przedziału 1... n, pooddzielanych pojedynczymi odstępami; i-ty wyraz ciągu oznacza numer żetonu, na który mają skakać pchły z żetonu nr i.

Wyjście

• T - jeśli oba zestawy żetonów można ułożyć tak, aby pchły wykonały taki sam taniec,
• N - w przeciwnym wypadku.

Przykład

2
3
2 3 1
2 3 3
4
2 3 2 4
1 3 2 3

N
T

Rozwiązanie

Wypada nam zacząć od przypomnienia, co to jest graf.

Graf są to kropki, z których niektóre połączone są strzałkami. Albo inaczej: graf G jest to para uporządkowana , gdzie V jest dowolnym zbiorem, który nazwiemy zbiorem wierzchołków grafu, zaś jest zbiorem krawędzi: jeżeli są dwoma wierzchołkami grafu, to są one połączone strzałką od v do v' wtedy i tylko wtedy, gdy para .

Zwróćmy uwagę, że w przyjętej przez nas definicji krawędź od v do v' to nie to samo, co krawędź od v' do v. Ponadto, dopuszczamy pętle, czyli krawędzie prowadzące od wierzchołka do niego samego.

Grafy są przydatne do opisu wielu praktycznych zagadnień, np. sieci komunikacyjnych, obwodów elektrycznych, zależności pomiędzy etapami przedsięwzięcia, a także, jak się zaraz okaże, pchlej choreografii.

Kiedy rysujemy graf, zazwyczaj nie ma dla nas znaczenia, jak na naszym rysunku rozmieszczone są wierzchołki, ważne jest tylko, które z którymi są połączone. Poza tym często wszystkie wierzchołki grafu zaznaczamy tak samo (np. kropką). Stąd pojawia się problem izomorfizmu grafów, polegający na rozstrzygnięciu, czy dane dwa grafy da się narysować tak samo? Innymi słowy, chodzi o sparowanie wierzchołków grafu G₁ z wierzchołkami grafu G₂ tak, by krawędzie w grafie G₁ dokładnie odpowiadały krawędziom pomiędzy wierzchołkami do pary w grafie G₂. Jeszcze inaczej, chodzi o znalezienie funkcji wzajemnie jednoznacznej takiej, by zachodziło wtedy i tylko wtedy, gdy .

Wróćmy teraz do naszego zadania. Mamy opis pewnego tańca pcheł, czyli n żetonów ponumerowanych liczbami 1,2,...,n, a na każdym z nich dodatkową liczbę mówiącą, na który żeton pchła ma skoczyć. Rozważmy graf, którego zbiorem wierzchołków będzie właśnie , czyli każdemu żetonowi odpowiada dokładnie jeden wierzchołek grafu. Krawędzie poprowadzimy oczywiście od każdego żetonu do tego, którego numer jest na nim zapisany. Krawędzie będą zatem odpowiadać pchlim skokom.

Teraz naprawdę nietrudno zauważyć, że nasze zadanie to po prostu pytanie o izomorfizm tak utworzonych grafów! Zaglądamy zatem do indeksu dowolnego podręcznika algorytmiki, znajdujemy hasło ,,grafów izomorfizm'' i ... co za rozczarowanie! Okazuje się, że nie jest znany żaden wielomianowy algorytm na rozstrzyganie o izomorfizmie grafów. Nikt też nie zdołał udowodnić, że taki algorytm nie może istnieć, co więcej nie wiadomo nawet, czy jest to tzw.problem NP-zupełny.(Problemy NP-zupełne to m.in. problem cyklu Hamiltona, problem komiwojażera, problem 3-kolorowania grafu, sumy podzbioru, maksymalnej kliki, spełnialności formuł boolowskich i kilkaset innych. Wiadomo o tych problemach tyle, że albo wszystkie mają rozwiązania wielomianowe, albo żaden z nich takiego rozwiązania nie ma. Ponieważ przez wiele lat nie wymyślono dla żadnego z nich algorytmu wielomianowego (za to wymyślono wiele naprawdę pomysłowych algorytmów dla innych problemów), więc większość informatyków przypuszcza, że takie algorytmy nie istnieją. Wciąż jednak nikt nie potrafi tego udowodnić. Więcej o problemach NP i NP-zupełnych można poczytać w znakomitej książce [14].)

Czyżby było aż tak źle? Pomyślmy... niektórzy spośród czytelników słyszeli może o problemie izomorfizmu drzew, dla którego istnieje rozwiązanie wielomianowe. Drzewa to grafy bez cykli. Być może grafy, które opisują pchle harce, też mają jakąś szczególną postać, która pozwala łatwo rozwiązać nasz problem? Okazuje się, że tak.

Przede wszystkim, w naszych grafach z każdego wierzchołka wychodzi dokładnie jedna krawędź. Oczywiście jest całe mnóstwo grafów, które nie mają tej właściwości, np. trzy spośród czterech narysowanych powyżej.

Zdefiniujmy cykl (skierowany) jako ciąg (v₁,v₂,...,v_n) parami różnych wierzchołków grafu taki, że dla każdego i=1,2,...,n-1 mamy w grafie krawędź oraz dodatkowo . Zauważmy, że jeżeli ciąg (v₁,v₂,...,v_n) jest cyklem, to dla każdego i=2,3,..., n cyklem jest także ciąg , otrzymany przez cykliczne przesunięcie ciągu wyjściowego w lewo o i-1 pozycji. Umówmy się, że są to równoważne reprezentacje jednego i tego samego cyklu.

A co możemy powiedzieć o cyklach w naszych pchlich grafach? Wykażemy, że są one rozłączne, to znaczy że każdy wierzchołek należy do co najwyżej jednego cyklu. Dlaczego? Przypuśćmy, że wierzchołek v=v_i=v'_j należy do dwóch cykli: v₁,v₂,...,v_n oraz v'₁,v'₂,...,v'_m. Umówiliśmy się, że ciągi reprezentujące cykle możemy przesuwać cyklicznie, zatem nic nie stracimy zakładając, że v=v₁=v'₁ (czyli że i=j=1). Zamieniając w razie potrzeby cykle rolami możemy również przyjąć, że . Wiemy, że z wierzchołka v (podobnie jak z każdego innego) wychodzi dokładnie jedna krawędź, wiemy też, że mamy w naszym grafie krawędź (v₁,v₂) oraz (v'₁,v'₂). Skoro zatem v=v₁=v'₁, to także v₂=v'₂. Rozumując tak dalej wnioskujemy, że v₃=v'₃,..., v_n=v'_n. Jeżeli byłoby m>n, to mielibyśmy następnie , lecz jest to niemożliwe, bo umówiliśmy się, że żaden wierzchołek w cyklu się nie powtarza. Czyli n=m i nasze cykle okazały się być jednym i tym samym cyklem (a nawet tą samą jego reprezentacją)!

Każdy wierzchołek w naszym grafie albo należy do jakiegoś jednego cyklu, albo nie należy do żadnego. Jak wygląda ten drugi przypadek? Niech wierzchołek v₁ nie należy do żadnego cyklu. Prowadzi z niego dokładnie jedna krawędź, umówmy się, że do wierzchołka v₂, z którego z kolei prowadzi krawędź do v₃ itd. Otrzymujemy ciąg wierzchołków v₁,v₂,v₃,v₄,.... Wiemy, że v₁ występuje tylko na początku ciągu (skoro nie leży na żadnym cyklu). Jednak w naszym grafie jest tylko skończenie wiele wierzchołków, więc od któregoś miejsca muszą się one zacząć powtarzać. Niech n będzie najmniejszą taką liczbą, że istnieje i<n takie, że v_i=v_n. Oczywiście i>1. Chwila uwagi wystarcza by stwierdzić, że wierzchołki tworzą cykl. Być może n=i+1, mamy wówczas cykl jednoelementowy, czyli pętlę przy wierzchołku v_i.

Podsumujmy: startując od dowolnego wierzchołka i podążając po strzałkach, albo jesteśmy od razu na cyklu, albo po jakimś czasie wpadamy na cykl. Sytuacja przypomina morza i rzeki: jeżeli jesteśmy w wodzie, to albo jesteśmy w morzu, i wtedy wiadomo w jakim, albo jesteśmy w rzece i w końcu spłyniemy do morza. Do tego wiadomo, w zlewisku jakiego morza leży dana rzeka. Co więcej, analogia obejmuje i to, że rzeka ma dopływy. Istotnie, ścieżki prowadzące od różnych wierzchołków do tego samego cyklu mogą się łączyć jeszcze przed osiągnięciem cyklu, tworząc podczepione do cykli drzewa. Przykładowo, wygląda to tak, jak na rysunku []. Wierzchołki, które leżą na cyklach, zaznaczono na szaro.