Strongly Connected Components (SCC) — Kosaraju's algorithm, Tarjan's algorithm

3.5.8 · Coding › Graphs

Exactly SCC kya hota hai?

Figure — Strongly Connected Components (SCC) — Kosaraju's algorithm, Tarjan's algorithm

Kosaraju's algorithm — DFS ke do passes

YEH KAAM KYUN KARTA HAI? (derive karo, memorize mat karo)

Finish times ke baare mein key fact. Maano SCCs $A$ aur $B$ hain, condensation mein edge $A \to B$ hai (toh $A$ DAG mein $B$ se "pehle" aata hai). Tab: $max_{u \in A} f (u) > max_{v \in B} f (v)$ yaani woh SCC jo DAG mein "pehle" hai, woh baad mein finish hoti hai.

Proof sketch (Yeh sach kyun hai):

Case 1: DFS pehle $A$ mein enter karta hai. Kyunki $A$ , $B$ ko reach kar sakta hai, DFS $A$ aur $B$ dono ko explore karega wapas aane se pehle, toh $A$ mein pehle touch kiya gaya node $B$ ki saari cheez ke baad finish hoga. ✓
Case 2: DFS pehle $B$ mein enter karta hai. Kyunki condensation ek DAG hai aur edge $A \to B$ jaati hai, $B \to A$ ka koi path nahi hai. Toh $B$ ki DFS poori tarah finish ho jaati hai $A$ ko touch kiye bina. Baad mein DFS $A$ mein start hoti hai → $A$ , $B$ ke baad finish hota hai. ✓

Ab graph reverse karo. $G^{rev}$ mein, edge $B \to A$ ban jaati hai. Doosri DFS hum highest finish time wale vertex se shuru karte hain — woh vertex original DAG ki "source" SCC mein hota hai (koi SCC baad mein finish nahi hoti). $G^{rev}$ mein woh SCC ek sink hai: doosri SCCs se uske edges reverse ho gaye hain aur ab us mein point karte hain, toh DFS doosri SCC mein escape nahi kar sakti. Isliye ek DFS tree = exactly ek SCC. Use hatao, repeat karo. ∎

Formula Kosaraju — pseudocode

order = []                      # fill by finish time
for each unvisited u: DFS1(u)   # on G; on return push u to order

Grev = reverse(G)
reverse(order)                  # decreasing finish time
for each u in order:
    if unvisited: DFS2(u) on Grev  # one whole tree = one SCC

Complexity: do DFS + ek reversal $= O (V + E)$ time, $O (V + E)$ space.

Tarjan's algorithm — DFS ka ek pass

`low[u] == disc[u]` ek root kyun mark karta hai

Hum current DFS path/SCC-candidates ki nodes ek explicit stack par rakhte hain, ek onStack[] flag ke saath.
low[u] kehta hai "sabse pehle discover hua node jo $u$ loop back kar sakta hai current SCC se bahar gaye bina."
Agar $u$ kisi pehle wale node tak pahunch sakta hai ( $l o w [u] < d i sc [u]$ ), toh $u$ apni SCC ka entry point nahi hai — koi ancestor hai.
Agar $u$ khud se upar nahi ja sakta ( $l o w [u] == d i sc [u]$ ), toh $u$ apni SCC ka highest node hai = uski root. Stack ko $u$ tak pop karo; woh vertices ek SCC hain.

Common mistake Classic blunders ko steel-man karna

1. "Tarjan: back/cross edges ke liye bhi low[v] use karo." Kyun sahi lagta hai: low hamesha "sabse gehri reachable" info carry karta hai, toh reuse kyun nahi? Fix: low[v] mein aisi node ho sakti hai jo stack se pehle hi pop ho gayi ho (ek alag, finished SCC). disc[v] use karna (sirf jab onStack[v] ho) aapko current component tak restrict karta hai, jo poora point hai. low[v] yahan use karna alag SCCs ko merge kar sakta hai.

2. "Kosaraju: doosri DFS pehle wali ke SAME order mein karo." Kyun sahi lagta hai: order toh order hota hai. Fix: theorem sirf decreasing finish time ke liye hold karta hai reversed graph par. Galat order ⇒ ek DFS tree doosri SCC mein leak ho sakta hai.

3. "SCC = connected components, bas directed graphs par." Kyun sahi lagta hai: names similar lagte hain. Fix: undirected connectivity ko sirf ek path chahiye; SCC ko dono taraf paths chahiye. Do nodes sirf $u \to v$ ke saath alag SCCs mein hain.

4. "onStack bhool jaana." Iske bina aap back-edge ko ek already-finished SCC mein treat karoge aisa jaise woh merge ho gaye.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho cities one-way roads se connected hain. Ek "club" un cities ka group hai jahan aap kisi bhi city se kisi bhi doosri city tak drive kar sako aur wapas aa sako — round trip hamesha possible ho. Woh club ek SCC hai. Kosaraju har city ko do baar explore karta hai: pehle log jis order mein apna tour finish karte hain woh note karne ke liye, phir woh saari road directions ulti kar deta hai aur jo sabse aakhir mein finish hua usse shuru karke re-tour karta hai — har naya tour exactly ek club fence kar deta hai. Tarjan woh smart traveler hai jo ek hi baar mein karta hai: woh "cities jahan mujhe abhi bhi wapas loop karna pad sakta hai" ka ek stack rakhta hai, aur jis moment use pata chalta hai ki ek city khud se purani kisi tak nahi pahunch sakti, woh jaanta hai ki woh city ek club ki leader hai aur stack se use aur upar waalon ko le leta hai.

Flashcards

Directed graph mein SCC kya hota hai?

Vertices ka ek maximal set jahan har pair mutually reachable ho (dono directions mein paths).

Graph ki condensation kya hoti hai?

Har SCC ko ek node mein contract karo; result hamesha ek DAG hota hai.

Kosaraju ke teen steps?

(1) G par DFS karo finish times record karte hue; (2) graph reverse karo; (3) reversed graph par decreasing finish-time order mein DFS karo — har tree ek SCC hai.

Kosaraju mein highest-finish-time vertex kyun matter karta hai?

Woh original DAG ki source SCC mein hota hai = reversed graph mein sink SCC, toh uski DFS tree doosri SCCs mein leak nahi kar sakti.

Tarjan mein low[u] ka matlab kya hai?

Sabse chhota discovery index jo u se tree edges plus at most ek aisi node tak edge ke zariye reachable hai jo abhi bhi stack par ho.

Tarjan mein SCC root ki condition?

low[u] == disc[u]; stack ko u tak aur u sameyt pop karo SCC banane ke liye.

Tarjan: low[v] vs disc[v] kab use karo?

Tree edges ke liye low[v] (recursive child); back/cross edges ke liye disc[v] sirf jab onStack[v] ho.

Dono algorithms ki time complexity?

O(V+E).

Tarjan mein onStack[] kyun zaroori hai?

Already-finished SCCs mein jaane wali edges ko ignore karne ke liye, taaki alag components merge na ho jaayein.

SCC aur undirected connected component mein farq?

SCC ko mutual (dono taraf) reachability chahiye; undirected components ko sirf ek single path chahiye.

Connections

Depth First Search — dono algorithms DFS skeletons hain.
Topological Sort — condensation DAG ko topologically order kiya ja sakta hai.
Directed Acyclic Graph (DAG) — SCCs contract karne ke baad jo milta hai.
2-SAT — implication graph par SCCs se solve hota hai.
Bridges and Articulation Points — Tarjan ka low-value idea undirected graphs par reuse hota hai.
Union-Find — alternative connectivity tool (sirf undirected ke liye).