Förberedelse inför kodningsintervjuer · Lektion

Starkt sammanhängande komponenter

Gruppera ömsesidigt nåbara noder med Tarjan

Lektion 3 av 413 steg

Starkt sammanhängande komponenter är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.

Vad en SCC är

En starkt sammanhängande komponent är en maximal grupp noder där varje nod kan nå alla andra genom att följa riktade kanter.

Varför det är viktigt

Om du slår ihop varje SCC till en supernod blir varje riktad graf en DAG. Då blir ömsesidiga beroenden enklare att analysera.

Tarjan i en genomgång

Tarjans algoritm hittar alla SCC:er med en enda DFS. Den körs på O(V + E), samma kostnad som en vanlig genomgång.

Upptäcktstal

Ge varje nod en upptäcktstid enligt den ordning som DFS besöker den första gången. Dessa id-värden låter dig jämföra vilken nod som upptäcktes tidigare.

disc = [-1] * n
timer = 0

Low-link-värdet

Varje nods low-link är det minsta upptäckts-id som kan nås från noden, även via bakåtkant. Det förankrar komponenten.

low = [-1] * n

Lägg noden på stacken

När DFS går in i en nod anger du dess disc och low och lägger sedan noden på en stack med noder som kan tillhöra samma komponent.

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

Uppdatera low från barnen

Efter rekursion på ett obesökt barn för du upp dess low-värde: low[u] blir minimum av sitt eget värde och barnets low-värde.

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

Hantera bakåtkant

Om en granne redan finns på stacken är den en föregångare i denna SCC. Använd dess disc för att sänka low[u].

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

Hitta komponentens rot

När low[u] är lika med disc[u] är nod u roten till en SCC. Alla noder ovanför den på stacken hör ihop.

Ta ut komponenten

Vid en rot ska du ta ut noder från stacken tills du tar bort u. Gruppen som tas ut är exakt en starkt sammanhängande komponent.

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

Kosaraju som alternativ

Föredrar du två genomgångar? Kosarajus algoritm kör DFS, vänder på varje kant och kör sedan DFS igen i avslutningsordning för att ta fram SCC:erna.

Snabb kontroll

Under Tarjans DFS gäller low[u] == disc[u] för nod u. Vad säger det dig?

Besvara frågan i den interaktiva lektionen

Sammanfattning: SCC:er med Tarjan

Följ disc och low i en enda DFS, lägg aktiva noder på stacken och ta ut en komponent när low är lika med disc. SCC:er i O(V+E). 🧩

Gratis att börja

Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 90
Lektioner: 360

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Starkt sammanhängande komponenter” gratis?

Ja – hela texten till ”Starkt sammanhängande komponenter” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.

Vad lär jag mig i ”Starkt sammanhängande komponenter”?

Gruppera ömsesidigt nåbara noder med Tarjan Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?

Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.

Hur lång tid tar lektionen ”Starkt sammanhängande komponenter”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?

Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till Förberedelse inför kodningsintervjuer