Composantes connexes et remplissage par diffusion
Compter les îles et étiqueter les régions
Composantes connexes et remplissage par diffusion est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Ce qu’est une composante
Une composante connexe est un groupe de nœuds dont chacun est accessible depuis tous les autres. Un graphe peut contenir plusieurs groupes séparés. 🧩
Compter les composantes
Pour compter les composantes, lancez un parcours depuis chaque nœud non visité. Chaque nouveau départ marque un groupe entièrement nouveau.
Parcourir tous les nœuds
Parcourez les nœuds de 1 à n. Lorsque vous en trouvez un encore non visité, vous avez découvert une nouvelle composante à explorer.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1Un parcours par groupe
Le BFS ou DFS interne marque toute la composante comme visitée, si bien que la boucle externe l’ignore lors de son prochain passage.
Les grilles sont aussi des graphes
Une grille en deux dimensions est un graphe caché : chaque cellule est un nœud relié à ses voisines. Cela permet d’utiliser l’idée classique du remplissage par propagation. 🗺️
Les quatre directions
Depuis une cellule, vous vous déplacez généralement vers le haut, le bas, la gauche et la droite. Stockez ces déplacements sous forme de vecteurs de direction pour garder un code clair.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Rester dans la grille
Avant d'avancer, vérifiez que la nouvelle ligne et la nouvelle colonne sont dans les limites. Oublier cette vérification provoque des erreurs d'indice ou des réponses incorrectes.
if 0 <= nr < rows and 0 <= nc < cols:
passRemplir une seule région
Le remplissage par propagation commence sur une cellule et s'étend à toutes les cellules connectées du même type, comme l'outil de remplissage.
Compter les îles
Pour compter les îles, parcourez la grille ; à chaque nouvelle cellule terrestre, remplissez toute son île par propagation et ajoutez un au compteur.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Étiqueter les régions
Vous pouvez stocker une étiquette par cellule pendant le remplissage. Ensuite, vous savez instantanément à quelle région appartient chaque cellule.
Linéaire par rapport à la taille de la grille
Chaque cellule est visitée une fois : le remplissage par propagation d'une grille s'exécute donc en O(lignes fois colonnes). Cette complexité respecte largement les limites des concours.
Vérification rapide
Comment comptez-vous les composantes connexes ?
Récapitulatif
Vous comptez les composantes en parcourant chaque nœud non visité, et vous utilisez le remplissage par propagation sur les grilles pour étiqueter les régions et compter les îles. 🎉
Questions Fréquemment Posées
La leçon « Composantes connexes et remplissage par diffusion » est-elle gratuite ?
Oui — le texte complet de « Composantes connexes et remplissage par diffusion » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Composantes connexes et remplissage par diffusion » ?
Compter les îles et étiqueter les régions Tu pratiques Coding Interview Prep 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep 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 4 sur 4.
Combien de temps prend la leçon « Composantes connexes et remplissage par diffusion » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep 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
- Listes d’adjacence à partir de l’entrée
- BFS pour les plus courts chemins non pondérés
- DFS, récursion et piles itératives
- Composantes connexes et remplissage par diffusion