What are Strongly Connected Components?
Learn strongly connected components, Tarjan's and Kosaraju's algorithms, and how to answer this directed graph interview question.
Expected Interview Answer
A strongly connected component (SCC) is a maximal set of vertices in a directed graph where every vertex can reach every other vertex in the set via a directed path, and the standard algorithms to find all SCCs are Tarjan's algorithm (single DFS pass, O(V + E)) and Kosaraju's algorithm (two DFS passes on the graph and its transpose, also O(V + E)).
SCCs only matter for directed graphs, since in an undirected graph connectivity is already symmetric. Tarjan's algorithm does a single DFS while tracking a discovery-time index and a low-link value per vertex — the lowest index reachable back up through the DFS tree, including via back edges — and pops a full SCC off an explicit stack whenever a vertex's low-link equals its own index. Kosaraju's algorithm instead runs DFS once to compute a finishing-time ordering, reverses every edge in the graph, then runs DFS again in decreasing finish-time order on the reversed graph, with each resulting DFS tree forming one SCC. Collapsing each SCC into a single node produces a DAG, which is a common preprocessing step before running topological sort or dependency analysis on cyclic directed graphs.
- Identifies mutually reachable vertex groups in one linear pass
- Collapsing SCCs turns a cyclic graph into a DAG
- Reveals circular dependencies in package/module graphs
- Both algorithms run in optimal O(V + E) time
AI Mentor Explanation
Strongly connected components are like grouping cricket teams into clusters where every team in a cluster has, at some point, both beaten and lost to every other team in that same cluster through some chain of results — a closed loop of rivalry. A team outside the cluster that only ever beat teams in it, without ever losing to any of them, stays in its own separate cluster because the reachability only flows one way. Tarjan's approach is like a single pass through the season's results, tagging each team with how far back up the chain of wins it can trace a loop, and sealing off a cluster the moment a team can't reach any earlier team. This mirrors exactly how SCCs group only the teams that are mutually reachable through directed win chains.
Step-by-Step Explanation
Step 1
Run a single DFS, tracking discovery index and low-link
Tarjan's algorithm assigns each vertex a discovery index and a low-link value updated via tree and back edges.
Step 2
Maintain an explicit stack of active vertices
Push each vertex on first visit; keep it on the stack while still part of the current DFS exploration.
Step 3
Pop an SCC when low-link equals discovery index
When a vertex's low-link matches its own discovery index, pop the stack down to it — that group is one SCC.
Step 4
Alternatively, use Kosaraju: DFS, transpose, DFS again
Record finish order, reverse all edges, then DFS in decreasing finish order — each resulting tree is one SCC.
What Interviewer Expects
- Define SCC precisely: mutual reachability, directed graphs only
- Explain either Tarjan's low-link logic or Kosaraju's two-pass structure
- State both run in O(V + E) time
- Give a real use case: circular dependency detection, condensing a graph into a DAG
Common Mistakes
- Applying SCC concepts to an undirected graph (connected components suffice there)
- Confusing low-link value with discovery index in Tarjan's algorithm
- Forgetting to reverse the graph before the second DFS pass in Kosaraju
- Assuming a single DFS without a stack can find SCCs directly
Best Answer (HR Friendly)
“A strongly connected component is a group of nodes in a directed graph where you can get from any node to any other node in the group and back. I would use Tarjan's algorithm for a single efficient pass, and I've seen this concept used in practice to detect circular dependencies between software modules.”
Code Example
def tarjan_scc(graph, num_vertices):
index_counter = [0]
index = {}
lowlink = {}
on_stack = {}
stack = []
result = []
def strongconnect(v):
index[v] = index_counter[0]
lowlink[v] = index_counter[0]
index_counter[0] += 1
stack.append(v)
on_stack[v] = True
for w in graph.get(v, []):
if w not in index:
strongconnect(w)
lowlink[v] = min(lowlink[v], lowlink[w])
elif on_stack.get(w):
lowlink[v] = min(lowlink[v], index[w])
if lowlink[v] == index[v]:
component = []
while True:
w = stack.pop()
on_stack[w] = False
component.append(w)
if w == v:
break
result.append(component)
for vertex in range(num_vertices):
if vertex not in index:
strongconnect(vertex)
return resultFollow-up Questions
- How would you condense a graph into a DAG using its SCCs?
- Walk through the difference between Tarjan's and Kosaraju's algorithms.
- How would you use SCCs to detect circular module dependencies in a build system?
- Why does SCC detection not apply meaningfully to undirected graphs?
MCQ Practice
1. A strongly connected component requires which property between its vertices?
SCC membership requires mutual reachability through some directed path, not direct edges or acyclicity.
2. What condition in Tarjan's algorithm signals that a vertex is the root of an SCC?
When low-link equals discovery index, no earlier vertex is reachable, so the stack is popped down to form one SCC.
3. What does Kosaraju's algorithm do between its two DFS passes?
Kosaraju's second pass runs on the transposed (edge-reversed) graph in decreasing finish-time order from the first pass.
Flash Cards
What defines a strongly connected component? — A maximal set of vertices where every vertex can reach every other vertex via a directed path.
Name the two standard SCC algorithms. — Tarjan's algorithm (single DFS pass) and Kosaraju's algorithm (two DFS passes on the graph and its transpose).
What does collapsing each SCC into one node produce? — A directed acyclic graph (DAG), useful for topological sort or dependency analysis.
What is a common real-world use of SCC detection? — Detecting circular dependencies between modules or packages.