Exercices corrigés — Unir & trouver, arbres couvrants (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Ce que la structure refuse de faire
- Les deux naïves, chiffrées
- Union par rang : dérouler
- La faute qui sépare au lieu d'unir
- Compresser sans récursion
- Kruskal, à la main
- Combien d'arbres couvrants minimaux ?
- Compter les composantes connexes
- Le rang ment, et c'est voulu
- La borne est atteinte
- Probleme – La structure complète, du contrat au coût mesuré
- Probleme – Kruskal : la propriété de la coupe, le code, et un piège d'OCaml
- Probleme – Le chemin le plus large
- Probleme – Unir \& trouver avec annulation
- Probleme – Regrouper par arbre couvrant