DSU avec compression de chemin
Trouver et fusionner en temps quasi constant
DSU avec compression de chemin est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Ce que gère un DSU
Un DSU regroupe des éléments dans des ensembles disjoints, afin de déterminer si deux éléments appartiennent déjà au même ensemble. 🤝
Les ensembles sous forme d'arbres
Un DSU stocke chaque ensemble sous forme d'arbre. Chaque élément pointe vers un parent, et le nœud le plus haut, la racine, est le nom unique du groupe entier.
Le tableau des parents
Vous stockez tous ces liens dans un seul tableau. Commencez avec chaque élément comme son propre parent : chaque élément appartient ainsi initialement à un ensemble distinct.
parent = list(range(n))Trouver la racine
L'opération find remonte les liens de parent jusqu'à ce qu'un élément pointe vers lui-même. Ce nœud qui pointe vers lui-même est la racine identifiant l'ensemble.
while parent[x] != x:
x = parent[x]Les longues chaînes posent problème
Sans précaution, les ensembles peuvent former de longues chaînes étroites. find doit alors parcourir les nœuds un par un, et une seule requête peut coûter O(n), ce qui est beaucoup trop lent.
Voici la compression de chemin
La compression de chemin résout ce problème : en recherchant la racine, vous faites pointer directement vers elle chaque nœud visité, ce qui aplatit l'arbre pour la prochaine fois. ⚡
Compression récursive
La méthode la plus claire est la récursion. Trouvez la racine, puis enregistrez-la dans parent[x] avant de renvoyer le résultat, afin de raccourcir définitivement le lien.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Deux éléments appartiennent-ils au même ensemble ?
Pour vérifier si deux éléments sont connectés, comparez leurs racines. Si find(a) est égal à find(b), ils appartiennent au même groupe ; sinon, ils sont encore séparés.
if find(a) == find(b):
print("connected")Fusionner deux ensembles
L'opération union réunit les groupes en faisant pointer une racine vers l'autre. Une seule instruction relie deux arbres entiers pour former un ensemble unique.
def union(a, b):
parent[find(a)] = find(b)Pourquoi est-ce si rapide ?
Avec la seule compression, les opérations s'exécutent en environ O(log n) temps amorti, et combinées au classement, elles atteignent un temps presque constant par requête.
Là où le DSU excelle
Le DSU permet de résoudre les problèmes de connexité : cercles d'amis, composantes d'un réseau et arbre couvrant de Kruskal reposent tous sur des opérations find et union rapides. 🌐
Vérification rapide
Réfléchissez à ce que la compression de chemin modifie réellement.
Récapitulatif
Vous avez construit un DSU : un tableau de parents, find pour obtenir la racine et union pour fusionner. La compression de chemin le garde extrêmement rapide. Beau travail ! 🎉
Questions Fréquemment Posées
La leçon « DSU avec compression de chemin » est-elle gratuite ?
Oui — le texte complet de « DSU avec compression de chemin » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « DSU avec compression de chemin » ?
Trouver et fusionner en temps quasi constant Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « DSU avec compression de chemin » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- DSU avec compression de chemin
- Union par rang et composantes
- Arbre couvrant minimal de Kruskal
- MST de Prim avec un tas