Componenti connesse e flood fill
Contare le isole ed etichettare le regioni
Componenti connesse e flood fill è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos’è una componente
Una componente connessa è un gruppo di nodi tali che ciascuno sia raggiungibile dagli altri. Un grafo può contenere diversi gruppi separati. 🧩
Contare le componenti
Per contare le componenti, si esegue una visita a partire da ogni nodo non visitato. Ogni nuovo punto di partenza identifica un nuovo gruppo completo.
Scorrere tutti i nodi
Si percorrono i nodi da 1 a n. Quando se ne trova uno ancora non visitato, si è scoperta una nuova componente da esplorare.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1Una visita per ogni gruppo
La BFS o DFS interna marca come visitata l’intera componente, quindi il ciclo esterno la salta alla visita successiva.
Anche le griglie sono grafi
Una griglia 2D è un grafo nascosto: ogni cella è un nodo collegato alle celle vicine. Questo introduce la classica tecnica del flood fill. 🗺️
Le quattro direzioni
Da una cella ci si sposta generalmente in alto, in basso, a sinistra e a destra. Si possono memorizzare questi spostamenti come vettori di direzione per mantenere il codice pulito.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Restare nella griglia
Prima di spostarsi, verifichi che la nuova riga e la nuova colonna siano entro i limiti. Saltare questo controllo causa errori di indice o risposte errate.
if 0 <= nr < rows and 0 <= nc < cols:
passRiempire una regione
Il flood fill parte da una cella e si espande a ogni cella connessa dello stesso tipo, proprio come lo strumento secchiello.
Contare le isole
Per contare le isole, scansioni la griglia; a ogni nuova cella di terra, esegua il flood fill sull'intera isola e incrementi il conteggio di uno.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Etichettare le regioni
Durante il riempimento può memorizzare un'etichetta per ogni cella. In seguito saprà immediatamente a quale regione appartiene ogni cella.
Lineare rispetto alle dimensioni della griglia
Ogni cella viene visitata una volta, quindi il flood fill su una griglia richiede O(righe per colonne). Questo rientra comodamente nei limiti delle gare.
Verifica rapida
Come si contano le componenti connesse?
Riepilogo
Le componenti si contano attraversando il grafo a partire da ogni nodo non visitato; sulle griglie, invece, si usa il flood fill per etichettare le regioni e contare le isole. 🎉
Domande Frequenti
La lezione «Componenti connesse e flood fill» è gratuita?
Sì — il testo completo di «Componenti connesse e flood fill» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Componenti connesse e flood fill»?
Contare le isole ed etichettare le regioni Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Componenti connesse e flood fill»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Liste di adiacenza dall’input
- BFS per i cammini minimi non pesati
- DFS, ricorsione e stack iterativi
- Componenti connesse e flood fill