Samenhangende componenten en flood fill
Eilanden tellen en gebieden labelen
Samenhangende componenten en flood fill is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat een component is
Een verbonden component is een groep knooppunten die je allemaal vanuit elkaar kunt bereiken. Een graaf kan meerdere afzonderlijke groepen bevatten. 🧩
Componenten tellen
Om componenten te tellen, voer je een doorloop uit vanaf elk nog niet bezochte knooppunt. Elke nieuwe start markeert één volledig nieuwe groep.
Alle knooppunten doorlopen
Loop door de knooppunten van 1 tot n. Als je er één vindt dat nog steeds unvisited is, heb je een nieuwe component ontdekt die je kunt verkennen.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1Eén doorloop per groep
Die interne BFS of DFS markeert de hele component als bezocht, zodat de buitenste lus die groep de volgende keer overslaat.
Rasters zijn ook grafen
Een tweedimensionaal raster is een verborgen graaf: elke cel is een knooppunt dat met zijn buren verbonden is. Zo krijg je het klassieke idee van vulling. 🗺️
De vier richtingen
Vanuit een cel ga je meestal omhoog, omlaag, naar links en naar rechts. Sla die bewegingen op als richtingvectoren om de code overzichtelijk te houden.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Blijf binnen het raster
Controleer voordat je een stap zet of de nieuwe rij en kolom binnen de grenzen vallen. Als je deze controle overslaat, krijg je indexfouten of verkeerde antwoorden.
if 0 <= nr < rows and 0 <= nc < cols:
passEén regio vullen met flood fill
Flood fill begint bij een cel en verspreidt zich naar elke verbonden cel van hetzelfde type, net als het verfemmertje.
Eilanden tellen
Om eilanden te tellen, doorloop je het raster. Bij elke nieuwe landcel vul je het hele eiland met flood fill en tel je er één bij op.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Regio's labelen
Je kunt tijdens het vullen per cel een label opslaan. Later weet je dan meteen tot welke regio een cel behoort.
Lineair in rastergrootte
Elke cel wordt één keer bezocht, dus flood fill over een raster draait in O(rijen maal kolommen). Dat past ruimschoots binnen de limieten van programmeerwedstrijden.
Snelle controle
Hoe tel je verbonden componenten?
Samenvatting
Je telt componenten door vanaf elke nog niet bezochte knoop te traverseren, en gebruikt flood fill op rasters om regio's te labelen en eilanden te tellen. 🎉
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Samenhangende componenten en flood fill” gratis?
Ja — de volledige tekst van “Samenhangende componenten en flood fill” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “Samenhangende componenten en flood fill”?
Eilanden tellen en gebieden labelen Je oefent met Competitive Programming Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Samenhangende componenten en flood fill”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Adjacentielijsten uit invoer
- BFS voor kortste ongewogen paden
- DFS, recursie en iteratieve stacks
- Samenhangende componenten en flood fill