Union par rang et composantes
Garder les arbres plats et compter les groupes
Union par rang et composantes est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 2 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 Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
L'opération union peut être paresseuse
L'opération union simple place une racine sous une autre. Si elle est mal effectuée, elle peut créer un arbre haut et lent : nous avons donc besoin d'une méthode plus intelligente pour fusionner les racines.
L'idée essentielle
L'union par rang attache toujours l'arbre le plus court sous le plus grand. Des arbres peu profonds rendent chaque opération find ultérieure plus rapide. 📏
Que signifie le rang ?
Le rang est une estimation de la hauteur d'un arbre. Chaque élément commence avec le rang 0, car un nœud seul n'a aucune profondeur en dessous de lui.
rank = [0] * nAttacher le plus court au plus grand
Comparez les rangs des deux racines. La racine de rang inférieur devient l'enfant, afin que l'arbre combiné reste aussi plat que possible.
if rank[ra] < rank[rb]:
parent[ra] = rbLes égalités augmentent le rang
Lorsque les deux racines ont un rang égal, choisissez l'une ou l'autre comme nouvelle racine et augmentez son rang de un, puisque l'arbre vient de gagner un niveau.
else:
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1Variante de l'union par taille
Une autre méthode courante est l'union par taille : attachez le plus petit ensemble sous le plus grand. Elle est tout aussi efficace et fournit gratuitement la taille des groupes.
Compter les composantes
Commencez un nombre égal à n, puisque chaque élément constitue son propre groupe. Chaque opération union réussie réunit deux groupes en un seul, vous devez donc le décrémenter.
components = nIgnorer les opérations union sans effet
Si deux éléments partagent déjà une racine, l'opération union n'a aucun effet. Ne diminuez le nombre que lorsque leurs racines diffèrent réellement.
if find(a) != find(b):
union(a, b)
components -= 1Rang et compression
Combinez l'union par rang avec la compression de chemin : le DSU s'exécute en temps inverse d'Ackermann, ce qui est effectivement constant pour toute entrée réelle. ⚡
Obtenir la taille des groupes à la demande
Avec l'union par taille, vous pouvez connaître instantanément la taille de n'importe quel groupe : il suffit de lire la taille stockée à la racine de l'élément.
group = size[find(x)]Utilité
Le comptage des composantes répond à des questions classiques, comme le nombre de cercles d'amis ou de régions connexes après une série d'appels de réunion. 🌐
Vérification rapide
Raisonnez sur l'évolution du compteur de composantes.
Récapitulatif
Vous avez appris la réunion par rang pour garder les arbres plats, ainsi que le suivi du nombre de composantes et de la taille des groupes. DSU est maintenant extrêmement rapide ! 🎉
Questions Fréquemment Posées
La leçon « Union par rang et composantes » est-elle gratuite ?
Oui — le texte complet de « Union par rang et composantes » 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 Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Union par rang et composantes » ?
Garder les arbres plats et compter les groupes Tu pratiques Competitive Programming Academy 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 Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy 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 2 sur 4.
Combien de temps prend la leçon « Union par rang et composantes » ?
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 Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy 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