PricingLoginStart free
Competitive Programming Academy · leksjon

Union by Rank og komponenter

Hold trærne flate og tell grupper

Leksjon 2 av 413 trinn

Union by Rank og komponenter er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.

Union kan være naiv

En enkel union henger bare én rot under en annen. Hvis dette gjøres uforsiktig, kan det bygge et høyt og tregt tre, så vi trenger en smartere måte å slå sammen røtter på.

Hovedideen

Union by rank fester alltid det kortere treet under det høyere. Når trærne holdes grunne, blir alle senere find-operasjoner raskere. 📏

Hva rank betyr

Rank er et estimat på høyden til et tre. Hvert element starter med rank 0, siden én enkelt node ikke har noen dybde under seg.

rank = [0] * n

Fest det kortere under det høyere

Sammenlign rank-verdiene til de to røttene. Roten med lavest rank blir barnet, slik at det sammenslåtte treet holder seg så flatt som mulig.

if rank[ra] < rank[rb]:
    parent[ra] = rb

Lik rank øker rangen

Når begge røttene har samme rank, velger Du én av dem som ny rot og øker ranken med én, siden treet nettopp ble ett nivå høyere.

else:
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1

Varianten union by size

Et populært alternativ er union by size: fest den mindre mengden under den større. Det er like effektivt og gir gruppestørrelsene uten ekstra kostnad.

Tell komponenter

Start et antall på n, siden hvert element er sin egen gruppe. Hver vellykkede union slår sammen to grupper til én, så Du reduserer antallet.

components = n

Hopp over union-operasjoner uten effekt

Hvis to elementer allerede deler en rot, gjør union ingenting. Reduser bare antallet når røttene faktisk er forskjellige.

if find(a) != find(b):
    union(a, b)
    components -= 1

Rank pluss komprimering

Kombiner union by rank med path compression, så kjører DSU på invers-Ackermann-tid, som i praksis er konstant for alle reelle inndata. ⚡

Gruppestørrelser ved behov

Med union by size kan Du svare umiddelbart på hvor stor en gruppe er: les bare av size som er lagret ved elementets rot.

group = size[find(x)]

Hvor dette er nyttig

Komponenttelling besvarer klassiske spørsmål som hvor mange vennekretser eller sammenhengende regioner det finnes etter en rekke union-kall. 🌐

Rask sjekk

Tenk gjennom hvordan komponenttelleren endres.

Besvar den i den interaktive leksjonen

Oppsummering

Du lærte union by rank for å holde trærne flate, og hvordan du sporer antall komponenter og gruppestørrelser. DSU er nå lynrask! 🎉

Gratis å komme i gang

Lær deg Python med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs
30
Leksjoner
120
Start læringen gratisSe hele kurset

Ofte stilte spørsmål

Er leksjonen «Union by Rank og komponenter» gratis?

Ja – hele teksten i «Union by Rank og komponenter» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Union by Rank og komponenter»?

Hold trærne flate og tell grupper Du øver på Competitive Programming Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Competitive Programming Academy?

Ingen tidligere erfaring er nødvendig. Competitive Programming Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.

Hvor lang tid tar leksjonen «Union by Rank og komponenter»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Competitive Programming Academy-leksjonen?

Ja. Alle Competitive Programming Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

  1. DSU med banekomprimering
  2. Union by Rank og komponenter
  3. Kruskal og minimalt spennende tre
  4. Prims MST med en heap
← Tilbake til Competitive Programming Academy