28.09.2009

28 września 2009

Find-Union i zastosowania

Prowadzący: Paweł Lipski

Na wykładzie przedstawiłem strukturę Find-Union wymyśloną przez Tarjana, służącą do przechowywania zbiorów rozłącznych, do których należą elementy o numerach ze zbioru ${1,\dots,n}$. Oprócz inicjalizującej $MakeSet$ można na niej wykonywać następujące operacje:

  • $Find(x)$, która zwraca reprezentanta elementu $x$. $Find(u) = Find(v)$ wtedy i tylko wtedy, gdy $u$ i $v$ należą do tego samego zbioru.
  • $Union(x, y)$, łącząca zbiory, do którego należy $x$ ze zbiorem, w którym jest $y$ (przy założeniu, że nie są to dwa te same zbiory).

Okazuje się, że ciąg m operacji (Find lub Union) można obsłużyć w czasie $o(m \log^* n)$, gdzie $\log^* n$ oznacza logarytm iterowany (oto wiki na jego temat) z $n$ - liczby elementów we wszystkich zbiorach. (Istnieje nawet mocniejsze ograniczenie). W praktyce więc zamortyzowany czas odpowiedzi można traktować jako stały (czyli jest on $\~O(1)$).

Find-Union ma bardzo bogate zastosowania, także na konkursach. Rozwiązania działające na zbiorach rozłącznych należą nieraz do "najładniejszych" algorytmów w ogóle. Na wykładzie omówiłem m. in.:

Strukturę Find-Union w implementacji Tarjana

Zastosowane heurystyki łączenia wg rang i kompresji ścieżek, omówiłem ich wpływ na czas działania.

Zadanie Małpki z X OI

Rozwiązanie wzorcowe offline, działające "od tyłu".

Problem: Mikromiętus

Mamy planszę z $n, n \le 10^6$ polami. Na planszy są stawiane kolejno pionki. Wybieramy sobie coraz to nowe pola, na które chcemy postawić pionek. Jeśli wybrane pole jest wolne od pionka, to stawiamy na nim pionek. Jeśli na polu, na które chcemy postawić pionek, znajduje się już jakiś inny pionek, to dostajemy z banku tyle tarjalarów, ile wynosi odległość do najbliższego wolnego pola. Mamy ciąg co najwyżej $n$ próśb o postawienie pionka. Naszym zadaniem jest policzenie, ile pieniędzy otrzymamy po odpowiedzeniu na wszystkie prośby.

Problem: Offline Insert-Extract Minimum

Mamy zbiór $S$, początkowo pusty oraz ciąg $2n, n \le 10^6$ zapytań postaci: "Wstaw $a, 1 \le a \le n$ do zbioru $S$" lub "Usuń ze zbioru $S$ najmniejszy element i wypisz go". Każda liczba z zbioru ${ 1, \dots, n }$ pojawi się w zapytaniach o wstawienie dokładnie raz, więc zarówno zapytań o usunięcie, jak i o wstawienie będzie dokładnie $n$. Operacje będą wykonywane po kolei. Należy odpowiedzieć, jaka liczba zostanie wypisana w każdym z zapytań o usunięcie. Można to zrobić oczywiście w czasie $O(n \log n)$ przy użyciu jakiegoś kopca, ale da szybciej, prawie że liniowo - pomocny będzie oczywiście Find-Union. Aha, oczywiście możemy działać offline - najpierw wczytać wszystkie zapytania, potem dopiero udzielić wszystkich odpowiedzi.