Poniższe zadanie można rozwiązać w zadowalający sposób na kilka różnych sposobów. W tym laboratorium proponujemy rozwiązanie używające struktury danych dla zbiorów rozłącznych, ale i nie tylko.
Zadanie INW (Graf inwersji)
Dostępna pamięć: 128MB.
Bajtazar odkrył nową rodzinę grafów nieskierowanych, które można reprezentować za pomocą inwersji. Niech \( \displaystyle V = \{1,2,\ldots,n\} \) będzie zbiorem wierzchołków grafu, natomiast \( \displaystyle a_1,a_2,\ldots,a_n \) - pewnym ciągiem parami różnych liczb ze zbioru \( \displaystyle V \). Wierzchołki \( \displaystyle a_i \) oraz \( \displaystyle a_j \) są połączone krawędzią w grafie, jeśli para \( \displaystyle (i,j) \) jest inwersją w tym ciągu, to znaczy \( \displaystyle i < j \) oraz \( \displaystyle a_i > a_j \).
Dla przykładu rozważmy \( \displaystyle n=4 \) i ciąg 2, 3, 1, 4. Wtedy uzyskujemy graf jak na rysunku:
Bajtazar chce pokazać, że wymyślona przez niego reprezentacja jest użyteczna. Postanowił napisać program, który wyznacza spójne składowe grafu. Przypomnijmy, że dwa wierzchołki \( \displaystyle u,v\in V \) znajdują się w tej samej spójnej składowej grafu, jeśli istnieje taki ciąg wierzchołków, którego pierwszym wyrazem jest \( \displaystyle u \), ostatnim - \( \displaystyle v \), a każde dwa kolejne wierzchołki są połączone krawędzią grafu. W naszym przykładzie mamy dwie spójne składowe: \( \displaystyle \{1,2,3\} \) oraz \( \displaystyle \{4\} \).
Pomóż Bajtazarowi!
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita \( \displaystyle n \) ( \( \displaystyle 1 \leq n \leq 1\,000\,000 \) ) oznaczająca liczbę wierzchołków grafu. W drugim wierszu znajduje się ciąg \( \displaystyle n \) liczb całkowitych \( \displaystyle a_1, a_2, \ldots, a_n \).
Wyjście
W pierwszym wierszu wyjścia należy wypisać liczbę spójnych składowych grafu; oznaczmy tę liczbę przez \( \displaystyle m \). W każdym z kolejnych \( \displaystyle m \) wierszy należy podać opis jednej spójnej składowej grafu. Na początku wiersza wypisać należy liczbę \( \displaystyle k \) oznaczającą rozmiar składowej, a następnie rosnący ciąg \( \displaystyle k \) numerów wierzchołków tej składowej. Składowe należy wypisać w takiej kolejności, by pierwsze numery wierzchołków z każdego wiersza tworzyły ciąg rosnący. Innymi słowy, jeśli \( \displaystyle S \) i \( \displaystyle S' \) są dwiema składowymi, \( \displaystyle u \in S \), \( \displaystyle v\in S' \) są ich najmniejszymi wierzchołkami oraz \( \displaystyle uPrzykład
Dla danych wejściowych:
4
2 3 1 4
poprawnym wynikiem jest:
2
3 1 2 3
1 4