PricingLoginStart free
Competitive Programming Academy · Lekcja

Scalanie według rangi i składowe

Spłaszczanie drzew i zliczanie grup

Lekcja 2 z 413 kroki

Scalanie według rangi i składowe to bezpłatna lekcja Competitive Programming Academy 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 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.

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] * n

Podwieś 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] = rb

Remis 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] += 1

Wariant łą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 = n

Pomijaj 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 -= 1

Ranga 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.

Odpowiedz w interaktywnej lekcji

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! 🎉

Bezpłatny start

Ucz się Python dzięki korepetycjom AI — za darmo

Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.

Kursy
30
Lekcje
120
Zacznij naukę bezpłatnieWyświetl pełny kurs

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 Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Scalanie według rangi i składowe”?

Spłaszczanie drzew i zliczanie grup Ć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 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 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

  1. DSU z kompresją ścieżki
  2. Scalanie według rangi i składowe
  3. Minimalne drzewo rozpinające algorytmu Kruskala
  4. MST algorytmu Prima ze stosem kopcowym
← Powrót do Competitive Programming Academy