Composantes Connexes
Algorithmique classique
Enonce
Trouver toutes les composantes connexes d'un graphe non orienté. Retourner une liste de listes, chaque sous-liste contenant les sommets d'une composante.
Signature attendue
def composantes_connexes(graphe: dict) -> list:Exemple
composantes_connexes({0:[1], 1:[0], 2:[3], 3:[2], 4:[]})→[[0,1],[2,3],[4]]
📖 Rappel de cours
On lance un parcours depuis chaque sommet non encore visité : chaque parcours révèle une composante entière.
⚠ Le piège : Un seul parcours ne suffit pas — il ne voit que la composante du sommet de départ. La boucle externe sur tous les sommets est ce qui rend l'algorithme correct.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Parcours en Profondeur (DFS)
- Parcours en Largeur (BFS)
- Degré des Sommets
- Rendu de Monnaie Glouton
- Sélection d'Activités
- Sac à Dos Fractionnaire
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.