Sammenhengende komponenter og flomfylling
Tell øyer og merk regioner
Sammenhengende komponenter og flomfylling er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva en komponent er
En sammenhengende komponent er en gruppe noder som alle kan nå hverandre. En graf kan inneholde flere separate grupper. 🧩
Tell komponenter
For å telle komponenter kjøres en traversering fra hver ubesøkte node. Hver nye start finner én helt ny gruppe.
Gå gjennom alle noder
Gå gjennom nodene fra 1 til n. Når De finner en som fortsatt er ubesøkt, har De oppdaget en ny komponent som skal utforskes.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1Én traversering per gruppe
Den indre BFS-en eller DFS-en merker hele komponenten som besøkt, slik at den ytre løkken hopper over den neste gang.
Rutenett er også grafer
Et todimensjonalt rutenett er en skjult graf: hver celle er en node som er forbundet med naboene sine. Dette åpner for den klassiske ideen om flomfylling. 🗺️
De fire retningene
Fra en celle går De vanligvis opp, ned, til venstre eller til høyre. Lagre disse bevegelsene som retningsvektorer for å holde koden ryddig.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Hold deg innenfor rutenettet
Før du går videre, må du kontrollere at den nye raden og kolonnen er innenfor grensene. Hvis du hopper over denne kontrollen, kan du få indeksfeil eller feil svar.
if 0 <= nr < rows and 0 <= nc < cols:
passFyll ut én region
Flood fill starter i en celle og sprer seg til alle sammenhengende celler av samme type, akkurat som et malingsspannverktøy.
Tell øyer
For å telle øyer skanner du rutenettet. Når du finner en ny landcelle, fyller du ut hele øya med flood fill og øker antallet med én.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Merk regioner
Du kan lagre en etikett for hver celle mens du fyller ut. Senere vet du umiddelbart hvilken region en celle tilhører.
Lineær i rutenettets størrelse
Hver celle besøkes én gang, så flood fill på et rutenett bruker O(rader ganger kolonner). Det holder seg godt innenfor grensene i konkurranser.
Hurtigsjekk
Hvordan teller du sammenhengende komponenter?
Oppsummering
Du teller komponenter ved å traversere fra hver ubesøkte node, og bruker flood fill på rutenett for å merke regioner og telle øyer. 🎉
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Sammenhengende komponenter og flomfylling» gratis?
Ja – hele teksten i «Sammenhengende komponenter og flomfylling» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Sammenhengende komponenter og flomfylling»?
Tell øyer og merk regioner Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Sammenhengende komponenter og flomfylling»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Naboskapslister fra inndata
- BFS for korteste uvektede stier
- DFS, rekursjon og iterative stakker
- Sammenhengende komponenter og flomfylling