Exercices de programmation pour classes préparatoires
Ecrire une fonction composantes_connexes(graphe) qui renvoie le nombre de composantes connexes d'un graphe non oriente.
Representation : le graphe est represente par un dictionnaire d'adjacence {sommet: [voisins]}. Par exemple {0: [1], 1: [0], 2: []} represente un graphe avec deux composantes connexes : {0, 1} et {2}.
Rappel : une composante connexe est un ensemble maximal de sommets tels que pour toute paire de sommets de cet ensemble, il existe un chemin les reliant.
| Appel | Résultat attendu |
|---|---|
| composantes_connexes({0: [1], 1: [0], 2: []}) | 2 |
| composantes_connexes({0: [1, 2], 1: [0], 2: [0]}) | 1 |
Connectez-vous pour soumettre du code.