Componentes conexas y flood fill
Cuente islas y etiquete regiones
Componentes conexas y flood fill es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Qué es un componente
Un componente conexo es un grupo de nodos entre los que se puede llegar de uno a otro. Un grafo puede contener varios grupos separados. 🧩
Contar componentes
Para contar los componentes, ejecute un recorrido desde cada nodo no visitado. Cada nuevo inicio marca un grupo completamente nuevo.
Recorrer todos los nodos
Recorra los nodos del 1 al n. Cuando encuentre uno que siga sin visitar, habrá descubierto un componente nuevo que debe explorar.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1Un recorrido por grupo
Ese BFS o DFS interno marca como visitado todo el componente, por lo que el bucle externo lo omite la próxima vez.
Las cuadrículas también son grafos
Una cuadrícula 2D es un grafo oculto: cada celda es un nodo conectado con sus vecinos. Esto permite aplicar la idea clásica de flood fill. 🗺️
Las cuatro direcciones
Desde una celda normalmente puede moverse arriba, abajo, a la izquierda y a la derecha. Guarde esos movimientos como vectores de dirección para mantener el código limpio.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Manténgase dentro de la cuadrícula
Antes de avanzar, compruebe que la nueva fila y la nueva columna estén dentro de los límites. Omitir esta comprobación provoca errores de índice o respuestas incorrectas.
if 0 <= nr < rows and 0 <= nc < cols:
passRelleno de una región
El flood fill comienza en una celda y se extiende a todas las celdas conectadas del mismo tipo, como la herramienta de cubeta de pintura.
Conteo de islas
Para contar las islas, recorra la cuadrícula; al encontrar una nueva celda de tierra, aplique flood fill a toda su isla y sume uno al conteo.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Etiquetado de regiones
Puede almacenar una etiqueta por celda durante el relleno. Después sabrá al instante a qué región pertenece cualquier celda.
Lineal respecto al tamaño de la cuadrícula
Cada celda se visita una vez, por lo que el flood fill sobre una cuadrícula se ejecuta en O(filas por columnas). Esto se ajusta cómodamente a los límites de los concursos.
Comprobación rápida
¿Cómo cuenta las componentes conexas?
Repaso
Cuenta las componentes recorriendo cada nodo no visitado, y usa flood fill en cuadrículas para etiquetar regiones y contar islas. 🎉
Preguntas frecuentes
¿La lección «Componentes conexas y flood fill» es gratis?
Sí — el texto completo de «Componentes conexas y flood fill» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Componentes conexas y flood fill»?
Cuente islas y etiquete regiones Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Componentes conexas y flood fill»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Listas de adyacencia a partir de la entrada
- BFS para caminos mínimos no ponderados
- DFS, recursión y pilas iterativas
- Componentes conexas y flood fill