Componentes Conexos e Preenchimento por Inundação
Conte ilhas e rotule regiões.
Componentes Conexos e Preenchimento por Inundação é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O que é um componente
Um componente conexo é um grupo de nós em que todos podem alcançar uns aos outros. Um grafo pode conter vários grupos separados. 🧩
Contar componentes
Para contar componentes, execute uma travessia a partir de cada nó não visitado. Cada novo ponto inicial identifica um grupo completamente novo.
Percorrer todos os nós
Percorra os nós de 1 a n. Quando encontrar um ainda não visitado, você terá descoberto um novo componente para explorar.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1Uma travessia por grupo
Essa BFS ou DFS interna marca todo o componente como visitado, portanto o laço externo o ignora na próxima passagem.
Grades também são grafos
Uma grade 2D é um grafo oculto: cada célula é um nó ligado aos seus vizinhos. Isso permite usar a ideia clássica de preenchimento por inundação. 🗺️
As quatro direções
A partir de uma célula, normalmente você se move para cima, para baixo, para a esquerda e para a direita. Armazene esses movimentos como vetores de direção para manter o código organizado.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Permaneça dentro da grade
Antes de avançar, verifique se a nova linha e a nova coluna estão dentro dos limites. Ignorar essa verificação causa erros de índice ou respostas incorretas.
if 0 <= nr < rows and 0 <= nc < cols:
passPreencher uma região
O preenchimento por inundação começa em uma célula e se espalha para todas as células conectadas do mesmo tipo, assim como a ferramenta de balde de tinta.
Contar ilhas
Para contar ilhas, percorra a grade; em cada nova célula de terra, faça o preenchimento por inundação de toda a ilha e some um ao contador.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Rotular regiões
Você pode armazenar um rótulo por célula durante o preenchimento. Depois, saberá instantaneamente a qual região cada célula pertence.
Linear no tamanho da grade
Cada célula é visitada uma vez, então o preenchimento por inundação em uma grade é executado em O(linhas vezes colunas). Isso se ajusta tranquilamente aos limites de competições.
Verificação rápida
Como você conta componentes conexos?
Revisão
Você conta componentes percorrendo a partir de cada nó não visitado, e usa o preenchimento por inundação em grades para rotular regiões e contar ilhas. 🎉
Perguntas Frequentes
A aula “Componentes Conexos e Preenchimento por Inundação” é grátis?
Sim — o texto completo de “Componentes Conexos e Preenchimento por Inundação” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Componentes Conexos e Preenchimento por Inundação”?
Conte ilhas e rotule regiões. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Componentes Conexos e Preenchimento por Inundação”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Listas de Adjacência a partir da Entrada
- BFS para Caminhos Mínimos sem Pesos
- DFS, Recursão e Pilhas Iterativas
- Componentes Conexos e Preenchimento por Inundação