Intuition The one core ideaA strongly connected component (SCC) is a group of nodes in a one-way-road graph where you can drive from any node to any other and come back — round trips always exist. If you crush every such group into a single dot, the whole tangle of cycles collapses into a clean, cycle-free flowchart (a DAG), which is the real reason we hunt for SCCs at all.
Before you can understand Kosaraju or Tarjan, you need to see every piece of notation they lean on. This page builds each one from nothing, in the order the topic uses it. Nothing here is optional — the parent note silently assumes all of it.
Definition Directed graphA graph is a set of nodes (also called vertices ) connected by edges (lines). In a directed graph, every edge has an arrow : the edge u → v from u to v not back.
Picture cities joined by one-way streets . The arrow is the direction of legal travel.
Intuition Why arrows change everythingIn an ordinary (undirected) road you can walk both ways, so "can I get from A to B?" and "can I get from B to A?" are the same question. Add arrows and these become two separate questions . That single fact is what makes SCCs harder — and more interesting — than plain connectivity.
The symbol u → v u v
We write V number of vertices and E number of edges . When you see complexity O ( V + E )
Prerequisite: if the words node and edge are new, skim Depth First Search first — it walks these graphs.
Definition Path and reachabilityA path from u v u v u → x → y → v some path" into one symbol: u ⇝ v u v
The straight arrow → one edge. The squiggly arrow ⇝ any number of edges strung together (possibly through other nodes).
Worked example Reading the squiggleIf the edges are 1 → 2 2 → 3 1 ⇝ 3 true (go 1 → 2 → 3 no edge 1 → 3
→ ⇝ Why people trip: both are arrows. The fix: → ⇝ ⇝ getting there eventually , not in one hop.
Definition Mutually reachableTwo nodes u , v mutually reachable if both u ⇝ v and v ⇝ u
Look at the figure: the green cycle lets every node reach every other node and return, so all three are mutually reachable — they form one SCC. The lone orange node can be reached but you can never drive back , so it sits in its own SCC.
"Maximal " means you cannot add even one more node without breaking the property. The three green nodes are strongly connected; if you tried to add the orange node the round-trip property would fail — so the green trio is maximal and the orange node forms a separate size-1 SCC.
Every node belongs to exactly one SCC (even if that SCC is just itself). This "partition the whole graph" fact is what lets us later shrink each group to a single dot.
Intuition What DFS does, in one imageDFS = go as deep as you can, then back up. From a node, walk to an unvisited neighbour, from there to its unvisited neighbour, and so on until you hit a dead end. Then backtrack one step and try the next unexplored branch.
Two moments in a node's life matter, and the SCC algorithms name both:
Definition Discovery time and finish time
Discovery time disc[u] = the step number when DFS first arrives at u Finish time f(u) = the step number when DFS leaves u , i.e. after all of u
Intuition Why "finish" happens on the wayback up
A node is only "finished" once everything reachable below it has been explored. So finishing is a return event — you push the node onto an order list as you back out of it , not as you enter. Kosaraju's whole correctness proof rests on this ordering, so lock it in now.
visited[u] — a true/false flag: "have we touched u low[u] (Tarjan only) — a running "earliest node I can loop back to"; we build its full meaning in the D-later pages, but know now it is another number stored per node , computed during DFS.
Full walkthroughs live in Depth First Search .
onStack
A stack is a pile where you add and remove only from the top (last-in, first-out — like a stack of plates). Tarjan keeps every node it might still loop back to on this stack, with a flag onStack[u] marking membership. When it confirms an SCC, it pops (removes from the top) all those nodes at once.
Intuition Why a stack and not justvisited
visited says "seen ever." onStack says "seen and still part of the SCC currently being assembled ." A back-edge into a node that is visited but not on the stack points into an already-finished SCC and must be ignored — that distinction is exactly what a plain visited-flag cannot make.
A DAG = D irected A cyclic G raph: a directed graph with no cycles (you can never return to where you started). See Directed Acyclic Graph (DAG) .
Contract each SCC into one super-node. Draw an arrow C i → C j any original edge went from a node of C i C j always a DAG — because if it had a cycle, those SCCs could reach each other both ways and would already have merged into one SCC.
Cycles make graph problems hard. Once the graph is a DAG you get a valid ordering (see Topological Sort ), and problems like longest path, 2-SAT solving, and dependency resolution become easy. SCC is the standard "remove the cycles" pre-processing step.
O ( V + E ) O ( ⋅ ) worst-case running time growth . O ( V + E )
Definition Reversed graphG rev every arrow: an edge u → v G v → u G rev unchanged by flipping (round trips stay round trips), but the direction between SCCs reverses — which is precisely the lever Kosaraju pulls in its second pass.
Mnemonic The symbol cheat-sheet→ ⇝ f ( u ) disc/low Tarjan numbers · onStack current-SCC flag · G rev
Directed graph: nodes and one-way edges
Path and reachability u to v
Mutual reachability both directions
SCC maximal mutually reachable group
Discovery time and finish time
Topological Sort and easy DAG problems
Cover the right side and test yourself.
What does the arrow u → v A single directed edge — legal travel from u v
What does the squiggle u ⇝ v There exists some path (any number of edges) from u v u v
When are two nodes in the same SCC? When they are mutually reachable: both u ⇝ v v ⇝ u
What does "maximal" add to the SCC definition? You cannot include any extra node without breaking the round-trip property.
What is f(u), the finish time, and when is it recorded? The step when DFS leaves u back up , after all descendants finish.
What is the difference between visited[u] and onStack[u]? visited = seen ever; onStack = seen and still part of the SCC currently being built .
What is G rev The graph with every edge reversed; within-SCC reachability is unchanged, but between-SCC direction flips.
Why is the condensation always a DAG? A cycle among super-nodes would mean those SCCs reach each other both ways, so they'd already be one SCC.
What does O ( V + E ) Running time grows in proportion to the number of nodes plus edges — linear in the graph's size.
