L'Atelier Monstre

L'Union-Find est une structure de données efficace pour gérer des ensembles disjoints, souvent utilisée pour modéliser des relatoins entre éléments. Dans cet article, nous explorons son application à deux problèmes classiques : la détermination du nombre maximum de héros dans un scénario de vérité et de mensonge, et la vérification de relations ...

Principe fondamental Transformer un arbre en une séquence linéaire où n'importe quel chemin correspond à au plus O(log n) segments consécutifs. Définitions essentielles Fils lourd : enfant dont la sous-arbre contient le plus de nœuds Fils léger : tout enfant n'étant pas fils lourd Arête lourde : reliant un nœud à son fils lourd Arête légère : ...