Sterk samenhangende componenten
Wederzijds bereikbare knooppunten met Tarjan groeperen
Sterk samenhangende componenten is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 3 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 SCC is
Een sterk samenhangende component is een maximale groep knopen waarin elke knoop elke andere kan bereiken door gerichte verbindingen te volgen.
Waarom dit belangrijk is
Door elke SCC samen te voegen tot één superknoop verandert elke gerichte graaf in een DAG. Daardoor zijn wederzijdse afhankelijkheden gemakkelijk te begrijpen.
Tarjan in één doorgang
Het algoritme van Tarjan vindt elke SCC in één DFS. Het draait in O(V + E), dezelfde kosten als één gewone doorloop.
Ontdekkingsnummers
Geef elke knoop een ontdekkingstijd in de volgorde waarin DFS die voor het eerst bezoekt. Met deze id's kun je vergelijken welke knoop eerder is gezien.
disc = [-1] * n
timer = 0De low-linkwaarde
De low-linkwaarde van elke knoop is de kleinste ontdekkings-id die vanuit die knoop bereikbaar is, ook via terugbogen. Die verankert de component.
low = [-1] * nOp de stapel plaatsen
Wanneer DFS een knoop binnengaat, stel je disc en low in en plaats je die op een stapel met knopen die mogelijk bij dezelfde component horen.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TrueDe low-waarde van kinderen bijwerken
Na recursie naar een niet-bezocht kind geef je de low-waarde ervan omhoog: low[u] wordt het minimum van zichzelf en de low-waarde van het kind.
dfs(v)
low[u] = min(low[u], low[v])Terugbogen verwerken
Als een buur al op de stapel staat, is die een voorouder in deze SCC. Gebruik zijn disc om low[u] te verlagen.
elif on_stack[v]:
low[u] = min(low[u], disc[v])De wortel van een component herkennen
Wanneer low[u] gelijk is aan disc[u], is knoop u de wortel van een SCC. Alles wat erboven op de stapel staat, hoort bij elkaar.
De component van de stapel halen
Bij een wortel haal je knopen van de stapel totdat je u verwijdert. Die groep is precies één sterk samenhangende component.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju als alternatief
Werk je liever in twee doorgangen? Kosaraju voert DFS uit, keert elke verbinding om en voert daarna opnieuw DFS uit in volgorde van afronding om SCC's los te maken.
Snelle controle
Tijdens Tarjans DFS voldoet knoop u aan low[u] == disc[u]. Wat vertelt dat je?
Herhaling: SCC's met Tarjan
Houd disc en low bij in één DFS, zet actieve knopen op een stapel en haal een component eraf zodra low gelijk is aan disc. SCC's in O(V+E). 🧩
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 “Sterk samenhangende componenten” gratis?
Ja — de volledige tekst van “Sterk samenhangende componenten” 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 “Sterk samenhangende componenten”?
Wederzijds bereikbare knooppunten met Tarjan groeperen 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 3 van 4.
Hoe lang duurt de les “Sterk samenhangende componenten”?
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
- Topologisch sorteren met het algoritme van Kahn
- Cycli in gerichte grafen detecteren
- Sterk samenhangende componenten
- Bruggen en articulatiepunten