Strongly Connected Components
Group mutually reachable nodes with Tarjan.
Strongly Connected Components is a free Competitive Programming Academy lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Competitive Programming Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What an SCC Is
A strongly connected component is a maximal group of nodes where every node can reach every other by following directed edges.
Why We Care
Collapsing each SCC into one supernode turns any directed graph into a DAG. That makes mutual dependencies easy to reason about.
Tarjan in One Pass
Tarjan's algorithm finds every SCC in a single DFS. It runs in O(V + E), the same cost as one plain traversal.
Discovery Numbers
Give each node a discovery time in the order DFS first visits it. These ids let you compare which node was seen earlier.
disc = [-1] * n
timer = 0The Low-Link Value
Each node's low-link is the smallest discovery id reachable from it, including through back edges. It anchors the component.
low = [-1] * nPush Onto the Stack
When DFS enters a node, set its disc and low, then push it onto a stack of nodes that might share its component.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TrueUpdate Low From Children
After recursing into an unvisited child, pull its low value up: low[u] becomes the minimum of itself and the child's low.
dfs(v)
low[u] = min(low[u], low[v])Handle Back Edges
If a neighbor is already on the stack, it is an ancestor in this SCC. Use its disc to lower low[u].
elif on_stack[v]:
low[u] = min(low[u], disc[v])Spot a Component Root
When low[u] equals disc[u], node u is the root of an SCC. Everything above it on the stack belongs together.
Pop the Component
At a root, pop nodes off the stack until you remove u. That popped group is exactly one strongly connected component.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju as an Alternative
Prefer two passes? Kosaraju's runs DFS, reverses every edge, then DFS again in finish order to peel off SCCs.
Quick Check
During Tarjan's DFS, node u satisfies low[u] == disc[u]. What does that tell you?
Recap: SCCs with Tarjan
Track disc and low in one DFS, stack live nodes, and pop a component whenever low equals disc. SCCs in O(V+E). 🧩
Frequently asked questions
Is the “Strongly Connected Components” lesson free?
Yes — the full text of “Strongly Connected Components” is free to read here on the web, and the Competitive Programming Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Competitive Programming Academy course, upgrade to CoddyKit PRO.
What will I learn in “Strongly Connected Components”?
Group mutually reachable nodes with Tarjan. You practise Competitive Programming Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Competitive Programming Academy?
No prior experience is required. Competitive Programming Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Strongly Connected Components” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Competitive Programming Academy lesson?
Yes. Every Competitive Programming Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Topological Sort with Kahn's Algorithm
- Detect Cycles in Directed Graphs
- Strongly Connected Components
- Bridges & Articulation Points