Algorytmy i struktury danych · Middle · Pytanie 34 z 75
Co obsługuje struktura union-find (zbiory rozłączne)?
- ✓Poprawna odpowiedź: Łączenie zbiorów i sprawdzanie, czy dwa elementy są w tym samym
- 2Sortowanie elementów i szukanie k-tego najmniejszego
- 3Przechowywanie par klucz-wartość z szybkimi zapytaniami o zakresy
Wyjaśnienie
union(a, b) łączy dwie grupy, a find(a) zwraca reprezentanta grupy. Z kompresją ścieżek i łączeniem według rangi obie są prawie O(1). Typowe zastosowania: spójne składowe, MST Kruskala, „czy te konta należą do tej samej osoby?”