Union per rango e componenti
Mantenere gli alberi piatti e contare i gruppi
Union per rango e componenti è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Union può essere pigra
La union semplice appende una radice sotto l'altra. Se eseguita senza attenzione, può creare un albero alto e lento; serve quindi un modo più intelligente per unire le radici.
L'idea fondamentale
La union by rank collega sempre l'albero più corto sotto quello più alto. Mantenere gli alberi bassi rende più veloce ogni find successivo. 📏
Che cosa significa rank
Il rank è una stima dell'altezza di un albero. Ogni elemento parte dal rank 0, perché un nodo singolo non ha profondità al di sotto di sé.
rank = [0] * nCollegare il più corto al più alto
Si confrontano i rank delle due radici. La radice con il rank minore diventa figlia, così l'albero risultante resta il più piatto possibile.
if rank[ra] < rank[rb]:
parent[ra] = rbIn caso di parità, il rank aumenta
Quando entrambe le radici hanno lo stesso rank, se ne sceglie una come nuova radice e si incrementa di uno il suo rank, perché l'albero è appena cresciuto di un livello.
else:
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1La variante union by size
Un'alternativa diffusa è la union by size: si collega l'insieme più piccolo sotto quello più grande. È altrettanto efficace e fornisce gratuitamente le dimensioni dei gruppi.
Contare le componenti
Si inizializza un conteggio a n, perché ogni elemento forma il proprio gruppo. Ogni union riuscita unisce due gruppi in uno, quindi il conteggio viene decrementato.
components = nSaltare le union senza effetto
Se due elementi condividono già la stessa radice, la union non fa nulla. Si diminuisce il conteggio soltanto quando le loro radici sono effettivamente diverse.
if find(a) != find(b):
union(a, b)
components -= 1Rank più compressione
Combini union by rank e compressione dei cammini: la DSU opera in tempo inverso di Ackermann, che per qualsiasi input reale è di fatto costante. ⚡
Dimensioni dei gruppi su richiesta
Con la union by size è possibile sapere immediatamente quanto è grande un gruppo: basta leggere la size memorizzata nella radice dell'elemento.
group = size[find(x)]Dove è utile
Il conteggio delle componenti risponde a domande classiche, come il numero di gruppi di amici o di regioni connesse dopo una sequenza di chiamate a union. 🌐
Verifica rapida
Ragionare su come cambia il conteggio delle componenti.
Riepilogo
Ha imparato a usare union by rank per mantenere gli alberi piatti e a tenere traccia del numero di componenti e delle dimensioni dei gruppi. La DSU è ora velocissima! 🎉
Domande Frequenti
La lezione «Union per rango e componenti» è gratuita?
Sì — il testo completo di «Union per rango e componenti» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Union per rango e componenti»?
Mantenere gli alberi piatti e contare i gruppi Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Union per rango e componenti»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- DSU con compressione dei cammini
- Union per rango e componenti
- Albero ricoprente minimo di Kruskal
- MST di Prim con un heap