DSU avec compression de chemin

Disjoint Set Union (DSU), également appelé union-find, est une structure de données qui gère une collection d'ensembles disjoints (sans chevauchement). Elle prend en charge deux opérations essentielles : find (à quel ensemble l'élément x appartient-il ?) et union (fusionner les ensembles contenant x et y). DSU est idéal pour les problèmes de connectivité dynamique, où les groupes fusionnent au fil du temps sans jamais être séparés.

Chaque élément commence dans son propre ensemble. À mesure que nous traitons les arêtes ou les relations, nous fusionnons les ensembles. Le défi consiste à effectuer ces opérations efficacement : les implémentations naïves sont en O(n) par opération, mais avec des optimisations, nous approchons O(1) en coût amorti.

Dans le DSU naïf, find(x) remonte la chaîne des parents jusqu'à atteindre un nœud qui pointe vers lui-même (la racine). Si l'arbre est équilibré, cela donne O(log n). Mais si nous effectuons toujours l'opération union en reliant la seconde racine sous la première, nous pouvons créer une chaîne (arbre dégénéré) de longueur n, ce qui rend chaque appel à find en O(n).

Considérons les opérations union successives 0→1→2→3→4. L'appel à find du nœud 0 doit parcourir toute la chaîne. Avec la compression de chemin, nous éliminons ce problème en faisant pointer directement vers la racine chaque nœud visité pendant l'opération find elle-même.

La compression de chemin modifie l'opération find afin qu'après avoir trouvé la racine, chaque nœud du chemin soit mis à jour pour pointer directement vers la racine. Les futurs appels à find sur ces nœuds deviennent O(1). La version récursive réalise cela élégamment en un seul passage.

L'idée essentielle est la suivante : lorsque l'appel récursif renvoie la racine, nous définissons self.parent[x] = root avant de retourner cette racine. Cela aplatit l'arbre : tous les nœuds du chemin de recherche pointent désormais directement vers la racine. Cela ne modifie pas l'ensemble auquel appartient un nœud ; cela raccourcit uniquement les futurs chemins de recherche.

La version itérative de la compression de chemin utilise deux passages : le premier remonte jusqu'à la racine ; le second repasse par chaque nœud du chemin et met à jour son parent pour qu'il pointe directement vers la racine. Cela évite le coût de la pile de récursion et reste sûr pour les arbres très profonds proches de la limite de récursion de Python.

Dans les approches récursive et itérative, la correction reste inchangée : find renvoie toujours la même racine. La seule différence réside dans la mise à jour des pointeurs vers les parents comme effet secondaire, ce qui rend tous les futurs appels à find sur ces nœuds égaux à O(1).

La compression de chemin seule atteint un temps amorti de O(log n) par opération sur une séquence de m opérations. Chaque opération find peut être coûteuse la première fois qu'une chaîne est parcourue, mais elle aplatit cette chaîne, de sorte que chaque appel à find ultérieur sur ces nœuds est en O(1). Le travail total est réparti sur de nombreuses opérations.

L'analyse formelle utilise la méthode de la fonction de potentiel : le potentiel du DSU diminue chaque fois que le parent d'un nœud est rapproché, et cette diminution paie le coût du parcours. Sans union par rang, la compression de chemin seule donne un coût amorti de O(log n), ce qui constitue déjà une énorme amélioration par rapport au coût naïf O(n).

Une application courante du DSU consiste à compter les composantes connexes d'un graphe. Nous initialisons un compteur components à n, soit une composante par nœud. Chaque opération union réussie (fusion de deux ensembles différents) décrémente le compteur de 1. À la fin, le compteur contient le nombre de composantes distinctes.

C'est plus efficace que d'exécuter BFS ou DFS pour les requêtes de connexité, en particulier lorsque les arêtes arrivent progressivement (en ligne). Le DSU traite chaque arête en un temps amorti presque égal à O(1), quel que soit le moment où elle arrive.

Le problème du nombre de provinces fournit une matrice d'adjacence n×n et demande combien de groupes de villes directement ou indirectement connectées existent. Il s'agit exactement d'un problème de composantes connexes que le DSU résout élégamment. Nous parcourons toutes les paires (i, j) pour lesquelles isConnected[i][j] == 1 et appelons union(i, j).

Après avoir traité toutes les connexions, dsu.components est la réponse. C'est plus simple et plus rapide que d'exécuter BFS depuis chaque nœud non visité, et cela traite directement la représentation matricielle sans construire d'abord une liste d'adjacence.

Au-delà de la compression en deux passages, il existe une variante plus simple en un seul passage appelée compression par moitié du chemin : lorsque nous remontons la chaîne, nous faisons pointer chaque nœud vers son grand-parent plutôt que vers son parent. Cela réduit de moitié la longueur du chemin à chaque parcours, sans second passage, et atteint la même complexité amortie O(alpha(n)) lorsqu'elle est combinée à l'union par rang.

La compression par moitié est souvent privilégiée en programmation compétitive, car elle se résume à une seule boucle claire, sans récursion ni second parcours. Chaque étape effectue self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x].

Pour vérifier si deux nœuds sont connected (dans la même composante), appelez find(x) == find(y). Si les deux appels renvoient la même racine, les nœuds appartiennent à la même composante. Il s'agit de la requête connected ; avec la compression de chemin, elle s'exécute en un temps amorti proche de O(1).

Dans les problèmes d'entretien, les requêtes de connexité sont souvent entremêlées avec des opérations union. Le DSU gère les deux en ligne : vous pouvez alterner les opérations union et les requêtes dans n'importe quel ordre. Cela distingue le DSU des algorithmes pour graphes statiques comme BFS/DFS, qui doivent être relancés après chaque modification structurelle.

Une erreur fréquente consiste à appeler find, puis à modifier incorrectement les parents. Appelez toujours find sur les deux éléments avant de vérifier leur égalité ; sinon, vous risquez de comparer incorrectement un nœud à sa propre racine. Une autre erreur consiste à oublier que union doit ne rien faire lorsque les deux éléments partagent déjà une racine.

En Python, la limite de profondeur de récursion (1000 par défaut) peut provoquer une RecursionError pour les longues chaînes avec un appel find récursif. Utilisez soit la version itérative en deux passages, soit augmentez la limite avec sys.setrecursionlimit, soit utilisez la compression par moitié de manière itérative afin d'éviter complètement une récursion profonde.

Dans certains problèmes, vous avez besoin de la taille de chaque composante, et pas seulement de sa racine. Ajoutez un tableau size initialisé à 1 partout. Lors de la fusion de deux composantes, ajoutez la taille de la racine la plus petite à celle de la racine la plus grande. Cela permet d'obtenir en O(1) la taille d'une composante après toute opération union.

Le suivi des tailles sert également de base à l'union par taille (une alternative à l'union par rang) : attachez toujours le plus petit arbre sous la racine du plus grand. Cela garantit que la hauteur de l'arbre reste en O(log n), offrant la même garantie asymptotique que l'union par rang.

Testez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation de cette leçon.

Dans cette leçon, vous avez appris que : le DSU maintient des ensembles disjoints grâce aux opérations find et union, la compression de chemin aplatit l'arbre en faisant pointer directement vers la racine tous les nœuds parcourus, et cela donne à find une performance amortie proche de O(1). Ensuite, nous étudierons l'union par rang, qui maintient les arbres peu profonds de haut en bas afin d'atteindre la borne de l'inverse d'Ackermann.