PricingLoginStart free
Competitive Programming Academy · leksjon

Sterkt sammenhengende komponenter

Gruppér gjensidig nåbare noder med Tarjan

Leksjon 3 av 413 trinn

Sterkt sammenhengende komponenter er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 3 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 Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.

Hva en SCC er

En sterkt sammenhengende komponent er en maksimal gruppe noder der hver node kan nå alle de andre ved å følge rettede kanter.

Hvorfor dette er nyttig

Hvis hver SCC slås sammen til én supernode, blir enhver rettet graf til en DAG. Da blir gjensidige avhengigheter enklere å forstå.

Tarjan i én gjennomgang

Tarjans algoritme finner alle SCC-er i én enkelt DFS. Den kjører på O(V + E), altså med samme kostnad som én vanlig gjennomgang.

Oppdagelsesnumre

Gi hver node en oppdagelsestid i den rekkefølgen DFS først besøker den. Disse ID-ene lar deg sammenligne hvilken node som ble besøkt først.

disc = [-1] * n
timer = 0

Low-link-verdien

Hver nodes low-link er den minste oppdagelses-ID-en som kan nås fra den, også via tilbakekanter. Den forankrer komponenten.

low = [-1] * n

Legg noden på stakken

Når DFS går inn i en node, setter du disc og low og legger den på en stakk med noder som kan tilhøre samme komponent.

disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = True

Oppdater low fra barna

Etter rekursjonen inn i et ubesøkt barn trekker du low-verdien opp: low[u] blir minimumet av sin egen verdi og barnets low.

dfs(v)
low[u] = min(low[u], low[v])

Behandle tilbakekanter

Hvis en nabo allerede er på stakken, er den en forfar i denne SCC-en. Bruk disc-verdien til å redusere low[u].

elif on_stack[v]:
    low[u] = min(low[u], disc[v])

Finn roten til en komponent

Når low[u] er lik disc[u], er node u roten til en SCC. Alt som ligger over den på stakken, tilhører samme komponent.

Ta komponenten av stakken

Ved en rot tar du noder av stakken til du har fjernet u. Gruppen som tas av, er nøyaktig én sterkt sammenhengende komponent.

while True:
    w = stack.pop()
    on_stack[w] = False
    comp.append(w)
    if w == u: break

Kosaraju som alternativ

Foretrekker du to gjennomganger? Kosarajus algoritme kjører DFS, snur alle kantene og kjører deretter DFS på nytt i ferdigstillingsrekkefølge for å finne SCC-ene.

Kort sjekk

Under Tarjans DFS oppfyller node u betingelsen low[u] == disc[u]. Hva forteller det deg?

Besvar den i den interaktive leksjonen

Oppsummering: SCC-er med Tarjan

Følg disc og low i én DFS, legg aktive noder på en stakk, og ta av en komponent hver gang low er lik disc. SCC-er på O(V+E). 🧩

Gratis å komme i gang

Lær deg Python 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
30
Leksjoner
120
Start læringen gratisSe hele kurset

Ofte stilte spørsmål

Er leksjonen «Sterkt sammenhengende komponenter» gratis?

Ja – hele teksten i «Sterkt sammenhengende komponenter» 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 Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Sterkt sammenhengende komponenter»?

Gruppér gjensidig nåbare noder med Tarjan Du øver på Competitive Programming Academy 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 Competitive Programming Academy?

Ingen tidligere erfaring er nødvendig. Competitive Programming Academy 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 3 av 4.

Hvor lang tid tar leksjonen «Sterkt sammenhengende komponenter»?

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 Competitive Programming Academy-leksjonen?

Ja. Alle Competitive Programming Academy-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

  1. Topologisk sortering med Kahns algoritme
  2. Finn sykluser i rettede grafer
  3. Sterkt sammenhengende komponenter
  4. Broer og artikulasjonspunkter
← Tilbake til Competitive Programming Academy