DSU con compressione dei cammini
Eseguire find e union in tempo quasi costante
DSU con compressione dei cammini è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cosa tiene traccia una DSU
Una Disjoint Set Union mantiene gli elementi raggruppati in insiemi non sovrapposti, così è possibile verificare se due elementi appartengono già allo stesso gruppo. 🤝
Gli insiemi come alberi
La DSU memorizza ogni insieme come un albero. Ogni elemento punta a un padre e il nodo più in alto, la radice, è il nome univoco dell'intero gruppo.
L'array dei padri
Tutti questi collegamenti vengono memorizzati in un unico array. Si inizia con ogni elemento come proprio padre, cioè ogni elemento appartiene inizialmente a un insieme separato.
parent = list(range(n))Trovare la radice
L'operazione find segue i collegamenti ai padri finché un elemento non punta a se stesso. Quel nodo che punta a se stesso è la radice che identifica l'insieme.
while parent[x] != x:
x = parent[x]Le catene lunghe rallentano
Senza le dovute precauzioni, gli insiemi possono formare catene lunghe e sottili. In tal caso find deve attraversare i nodi uno alla volta e una singola query può costare O(n), decisamente troppo.
Entra in gioco la compressione dei cammini
La compressione dei cammini risolve il problema: mentre si cerca la radice, ogni nodo visitato viene ricollegato direttamente alla radice, appiattendo l'albero per il futuro. ⚡
Compressione ricorsiva
Il modo più pulito è usare la ricorsione. Si trova la radice, poi la si memorizza in parent[x] prima di restituirla, accorciando definitivamente il collegamento.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Due elementi appartengono allo stesso insieme?
Per verificare se due elementi sono connessi, si confrontano le loro radici. Se find(a) equals find(b), appartengono allo stesso gruppo; altrimenti sono ancora separati.
if find(a) == find(b):
print("connected")Unire due insiemi
L'operazione union unisce i gruppi facendo puntare una radice all'altra. Una sola riga collega due alberi interi in un unico insieme.
def union(a, b):
parent[find(a)] = find(b)Perché è così veloce
Con la sola compressione, le operazioni richiedono circa O(log n) nel caso ammortizzato; insieme al ranking, raggiungono un tempo quasi costante per query.
Dove eccelle la DSU
La DSU è alla base dei problemi di connettività: gruppi di amici, componenti di rete e l'albero di copertura di Kruskal si affidano tutti a find e union veloci. 🌐
Verifica rapida
Rifletta su che cosa modifica realmente la compressione dei cammini.
Riepilogo
Ha costruito una DSU: un array dei padri, find per ottenere la radice e union per unire i gruppi. La compressione dei cammini la mantiene velocissima. Ottimo lavoro! 🎉
Domande Frequenti
La lezione «DSU con compressione dei cammini» è gratuita?
Sì — il testo completo di «DSU con compressione dei cammini» è 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «DSU con compressione dei cammini»?
Eseguire find e union in tempo quasi costante Eserciti Coding Interview Prep 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «DSU con compressione dei cammini»?
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 Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep 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