Scalanie według rangi i składowe
Spłaszczanie drzew i zliczanie grup
Scalanie według rangi i składowe to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Union może działać zachłannie
Zwykła operacja union po prostu podwiesza jeden korzeń pod drugim. Wykonana bez namysłu może zbudować wysokie, wolne drzewo, dlatego potrzebny jest sprytniejszy sposób na łączenie korzeni.
Główna idea
Łączenie według rangi zawsze podwiesza niższe drzewo pod wyższym. Utrzymywanie płytkich drzew przyspiesza każdą późniejszą operację find. 📏
Co oznacza ranga
Ranga jest przybliżeniem wysokości drzewa. Każdy element rozpoczyna z rangą 0, ponieważ pojedynczy węzeł nie ma pod sobą żadnego poziomu.
rank = [0] * nPodwieś niższe drzewo pod wyższym
Należy porównać rangi obu korzeni. Korzeń o mniejszej randze staje się dzieckiem, dzięki czemu połączone drzewo pozostaje możliwie płaskie.
if rank[ra] < rank[rb]:
parent[ra] = rbRemis zwiększa rangę
Gdy oba korzenie mają taką samą rangę, można wybrać dowolny z nich jako nowy korzeń i zwiększyć jego rangę o jeden, ponieważ drzewo właśnie urosło o jeden poziom.
else:
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1Wariant łączenia według rozmiaru
Popularną alternatywą jest łączenie według rozmiaru: mniejszy zbiór podwiesza się pod większym. Jest ono równie skuteczne i dodatkowo zapewnia rozmiary grup.
Zliczanie składowych
Należy rozpocząć licznik od n, ponieważ każdy element tworzy własną grupę. Każde udane połączenie scala dwie grupy w jedną, więc licznik trzeba zmniejszyć.
components = nPomijaj puste operacje union
Jeśli dwa elementy mają już wspólny korzeń, operacja union niczego nie zmienia. Licznik należy zmniejszać tylko wtedy, gdy ich korzenie faktycznie się różnią.
if find(a) != find(b):
union(a, b)
components -= 1Ranga plus kompresja
Połączenie łączenia według rangi z kompresją ścieżki sprawia, że DSU działa w czasie odwrotnie akermanowskim, który dla każdego rzeczywistego wejścia jest praktycznie stały. ⚡
Rozmiary grup na żądanie
Przy łączeniu według rozmiaru można natychmiast sprawdzić wielkość dowolnej grupy: wystarczy odczytać rozmiar przechowywany przy korzeniu tego elementu.
group = size[find(x)]Gdzie to się przydaje
Zliczanie składowych spójności pomaga odpowiadać na klasyczne pytania, takie jak liczba grup znajomych lub spójnych obszarów po wykonaniu serii operacji union. 🌐
Szybki test
Proszę przeanalizować, jak zmienia się licznik składowych.
Podsumowanie
Nauczył(a) się Pan/Pani stosować union by rank, aby utrzymywać drzewa w płaskiej postaci, a także śledzić liczbę składowych i rozmiary grup. DSU działa teraz błyskawicznie! 🎉
Często zadawane pytania
Czy lekcja „Scalanie według rangi i składowe” jest bezpłatna?
Tak — pełny tekst „Scalanie według rangi i składowe” 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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Scalanie według rangi i składowe”?
Spłaszczanie drzew i zliczanie grup Ćwiczysz Coding Interview Prep 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ąć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep 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 2 z 4.
Ile czasu zajmuje lekcja „Scalanie według rangi i składowe”?
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 Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep 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