DSU z kompresją ścieżki
Wyszukiwanie i scalanie w czasie niemal stałym
DSU z kompresją ścieżki to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co śledzi DSU
Disjoint Set Union przechowuje elementy w rozłącznych zbiorach, dzięki czemu można sprawdzić, czy dwie rzeczy już należą do tej samej grupy. 🤝
Zbiory jako drzewa
DSU przechowuje każdy zbiór jako drzewo. Każdy element wskazuje na rodzica, a węzeł znajdujący się najwyżej — korzeń — jest unikatową nazwą całej grupy.
Tablica rodziców
Wszystkie te powiązania są przechowywane w jednej tablicy. Na początku każdy element jest własnym rodzicem, co oznacza, że każda rzecz należy początkowo do osobnego zbioru.
parent = list(range(n))Znajdowanie korzenia
Operacja find przechodzi po połączeniach z rodzicami, aż znajdzie element wskazujący sam na siebie. Ten element jest korzeniem identyfikującym zbiór.
while parent[x] != x:
x = parent[x]Długie łańcuchy szkodzą
Bez odpowiednich zabezpieczeń zbiory mogą tworzyć długie, wąskie łańcuchy. Wtedy operacja find przechodzi przez węzły jeden po drugim, a pojedyncze zapytanie może kosztować O(n), co jest zdecydowanie zbyt wolne.
Wprowadzenie kompresji ścieżki
Kompresja ścieżki rozwiązuje ten problem: podczas znajdowania korzenia każdy odwiedzony węzeł zostaje bezpośrednio do niego przepięty, co spłaszcza drzewo przed kolejnym użyciem. ⚡
Rekurencyjna kompresja
Najczytelniej zrobić to rekurencyjnie. Należy znaleźć korzeń, a następnie zapisać go z powrotem w parent[x] przed zwróceniem wyniku, aby trwale skrócić połączenie.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Dwa elementy w tym samym zbiorze?
Aby sprawdzić, czy dwa elementy są połączone, należy porównać ich korzenie. Jeśli find(a) equals find(b), należą do tej samej grupy; w przeciwnym razie nadal są rozdzielone.
if find(a) == find(b):
print("connected")Łączenie dwóch zbiorów
Operacja union łączy grupy, wskazując jednym korzeniem na drugi. Jedna linia kodu łączy dwa całe drzewa w jeden zbiór.
def union(a, b):
parent[find(a)] = find(b)Dlaczego to działa tak szybko
Sama kompresja zapewnia amortyzowaną złożoność operacji w przybliżeniu O(log n), a w połączeniu z rangowaniem daje niemal stały czas pojedynczego zapytania.
Gdzie DSU sprawdza się najlepiej
DSU rozwiązuje problemy spójności: kręgi znajomych, składowe sieci oraz drzewo rozpinające Kruskala korzystają z szybkich operacji find i union. 🌐
Szybkie sprawdzenie
Zastanówmy się, co właściwie zmienia kompresja ścieżki.
Podsumowanie
Zbudowano DSU: tablicę rodziców, operację find do znajdowania korzenia i union do łączenia zbiorów. Kompresja ścieżki utrzymuje bardzo wysoką szybkość działania. Dobra robota! 🎉
Często zadawane pytania
Czy lekcja „DSU z kompresją ścieżki” jest bezpłatna?
Tak — pełny tekst „DSU z kompresją ścieżki” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „DSU z kompresją ścieżki”?
Wyszukiwanie i scalanie w czasie niemal stałym Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „DSU z kompresją ścieżki”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- DSU z kompresją ścieżki
- Scalanie według rangi i składowe
- Minimalne drzewo rozpinające algorytmu Kruskala
- MST algorytmu Prima ze stosem kopcowym