DSU con compressione dei cammini

Disjoint Set Union (DSU), chiamata anche Union-Find, è una struttura dati che gestisce una collezione di insiemi disgiunti (non sovrapposti). Supporta due operazioni fondamentali: find (a quale insieme appartiene l'elemento x?) e union (unisce gli insiemi che contengono x e y). DSU è ideale per i problemi di connettività dinamica, in cui i gruppi si uniscono nel tempo ma non vengono mai separati.

Ogni elemento inizia come insieme indipendente. Durante l'elaborazione di archi o relazioni, gli insiemi vengono uniti. La difficoltà consiste nell'eseguire queste operazioni in modo efficiente: le implementazioni ingenue richiedono O(n) per operazione, ma con le ottimizzazioni ci si avvicina a O(1) ammortizzato.

Nella DSU ingenua, find(x) risale la catena dei padri finché raggiunge un nodo che punta a sé stesso (la radice). Se l'albero è bilanciato, il costo è O(log n). Tuttavia, se si esegue sempre l'unione collegando la seconda radice sotto la prima, è possibile creare una catena (un albero degenere) di lunghezza n, rendendo ogni operazione find O(n).

Si consideri l'unione in sequenza di 0→1→2→3→4. La chiamata a find sul nodo 0 deve attraversare l'intera catena. Con la compressione dei cammini, si elimina questo problema facendo puntare direttamente alla radice ogni nodo visitato durante la stessa operazione find.

La compressione dei cammini modifica l'operazione find in modo che, dopo aver trovato la radice, ogni nodo lungo il cammino venga aggiornato affinché punti direttamente alla radice. Le chiamate find successive su questi nodi diventano O(1). La versione ricorsiva ottiene questo risultato elegantemente in un solo passaggio.

L'intuizione fondamentale è la seguente: quando la chiamata ricorsiva restituisce la radice, si assegna self.parent[x] = root prima di restituire il risultato. In questo modo si appiattisce l'albero: tutti i nodi del cammino di ricerca puntano ora direttamente alla radice. Questo non cambia l'insieme di appartenenza del nodo; accorcia soltanto i cammini delle ricerche successive.

La versione iterativa della compressione dei cammini usa due passaggi: nel primo si risale l'albero per trovare la radice; nel secondo si visita nuovamente ogni nodo del cammino e si aggiorna il suo padre affinché punti direttamente alla radice. In questo modo si evita il sovraccarico dello stack delle chiamate ricorsive ed è sicuro anche per alberi molto profondi, vicini al limite di ricorsione di Python.

Sia nell'approccio ricorsivo sia in quello iterativo la correttezza rimane invariata: find restituisce sempre la stessa radice. L'unica differenza consiste nell'aggiornamento dei puntatori ai padri come effetto collaterale, che rende O(1) tutte le operazioni find successive su quei nodi.

La sola compressione dei cammini raggiunge un tempo ammortizzato di O(log n) per operazione su una sequenza di m operazioni. La prima operazione find può essere costosa quando attraversa una catena, ma la appiattisce, così ogni operazione find successiva su quei nodi ha costo O(1). Il lavoro totale viene distribuito su molte operazioni.

L'analisi formale utilizza il metodo della funzione potenziale: il potenziale della DSU diminuisce ogni volta che il padre di un nodo si avvicina, e questa diminuzione copre il costo dell'attraversamento. Senza l'unione per rango, la sola compressione dei cammini offre un costo ammortizzato di O(log n): un miglioramento già enorme rispetto al costo ingenuo O(n).

Una delle applicazioni più comuni della DSU è il conteggio delle componenti connesse di un grafo. Si inizializza un contatore components uguale a n, uno per ogni nodo. Ogni operazione union eseguita con successo (che fonde due insiemi diversi) decrementa il contatore di 1. Al termine, il contatore contiene il numero di componenti distinte.

È più efficiente che eseguire BFS o DFS per le interrogazioni di connettività, soprattutto quando gli archi arrivano progressivamente (online). La DSU elabora ogni arco in un tempo ammortizzato quasi O(1), indipendentemente dal momento in cui arriva.

Il problema Number of Provinces fornisce una matrice di adiacenza n×n e chiede quante gruppi di città collegate direttamente o indirettamente esistano. Si tratta esattamente di un problema sulle componenti connesse, che la DSU risolve in modo diretto. Si iterano tutte le coppie (i, j) per cui isConnected[i][j] == 1 e si chiama union(i, j).

Dopo aver elaborato tutte le connessioni, dsu.components contiene la risposta. È più semplice e veloce che eseguire BFS a partire da ogni nodo non visitato e consente di gestire direttamente la rappresentazione tramite matrice, senza dover prima costruire una lista di adiacenza.

Oltre alla compressione in due passaggi, esiste una variante più semplice in un solo passaggio chiamata dimezzamento dei cammini: mentre si risale la catena, si fa puntare ogni nodo al proprio nonno invece che al proprio padre. In questo modo la lunghezza del cammino si dimezza a ogni attraversamento, senza un secondo passaggio, e si ottiene la stessa complessità ammortizzata O(alpha(n)) quando la tecnica è combinata con l'unione per rango.

Il dimezzamento dei cammini è spesso preferito nella programmazione competitiva perché consiste in un unico ciclo semplice, senza ricorsione né una seconda visita. A ogni passaggio si esegue self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x].

Per verificare se due nodi sono connessi (appartengono alla stessa componente), si chiama find(x) == find(y). Se entrambe le chiamate restituiscono la stessa radice, i nodi appartengono alla stessa componente. Questa è l'interrogazione di connettività e, con la compressione dei cammini, ha un tempo ammortizzato quasi O(1).

Nei problemi dei colloqui tecnici, le interrogazioni di connettività compaiono spesso intercalate alle operazioni union. La DSU gestisce entrambe online: è possibile alternare unioni e interrogazioni in qualsiasi ordine. Questa caratteristica distingue la DSU dagli algoritmi per grafi statici come BFS/DFS, che devono essere rieseguiti dopo ogni modifica strutturale.

Un errore frequente consiste nel chiamare find e poi modificare parent in modo errato. Si chiami sempre find su entrambi gli elementi prima di verificarne l'uguaglianza; in caso contrario, si potrebbe confrontare erroneamente un nodo con la propria radice. Un altro errore comune è dimenticare che union deve essere un'operazione nulla quando entrambi gli elementi condividono già la stessa radice.

In Python, il limite di profondità della ricorsione (1000 per impostazione predefinita) può causare un RecursionError per catene lunghe quando si usa una versione ricorsiva di find. Si può usare la versione iterativa in due passaggi, aumentare il limite con sys.setrecursionlimit oppure usare iterativamente il dimezzamento dei cammini per evitare del tutto la ricorsione profonda.

In alcuni problemi è necessaria la dimensione di ogni componente, non soltanto la sua radice. Si aggiunga un array size inizializzato con tutti valori pari a 1. Quando si fondono due componenti, si aggiunga la dimensione della radice più piccola a quella della radice più grande. Questo consente di ottenere in O(1) la dimensione di una componente dopo qualsiasi unione.

Il tracciamento delle dimensioni è anche alla base dell'unione per dimensione (un'alternativa all'unione per rango): si colleghi sempre l'albero più piccolo alla radice dell'albero più grande. In questo modo l'altezza dell'albero rimane O(log n), fornendo la stessa garanzia asintotica dell'unione per rango.

Verifichi la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.

In questa lezione ha imparato che: la DSU mantiene insiemi disgiunti con le operazioni find e union, la compressione dei cammini appiattisce l'albero facendo puntare direttamente alla radice tutti i nodi attraversati e ciò offre prestazioni ammortizzate quasi O(1) per find. Prossimamente esamineremo l'unione per rango, che mantiene gli alberi poco profondi dall'alto verso il basso e raggiunge il limite dato dalla funzione inversa di Ackermann.