Strongly Connected Components
A directed graph has n nodes, numbered 0 to n-1, and a list of edges, where [from, to] is an edge from node from to node to.
A strongly connected component is a largest group of nodes in which every node can reach every other node by following edges. Every node belongs to exactly one component, and a node on no cycle forms a component by itself. Return the number of strongly connected components.
Function
- ninteger
- the number of nodes
- edgesinteger-2d-array
- the directed edges, each as [from, to]
- Returnsinteger
- the number of strongly connected components
Constraints
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]with0 ≤ from, to < nandfrom ≠ to- No edge appears twice.
Examples
- Input
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- Output
- 3
- Explanation
- Nodes 0, 1 and 2 form a loop, so they reach each other. Nodes 3 and 4 point at each other. Node 5 reaches 4, but nothing comes back to 5, so it stands alone: 3 components.
- Input
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- Output
- 4
- Explanation
- Nodes 0 and 1 point at each other and form one component. The edge from 2 to 3 goes one way only, so 2 and 3 are separate, and node 4 has no edges at all: 4 components.
Follow-up
How few edges would you need to add to make the whole graph a single strongly connected component?
Hints
Open them one at a time. Each one gives away a little more.
Two nodes share a component exactly when each one can reach the other. A search from every node can test that, but it walks the same edges again and again. What can a single depth first search tell you about where a component begins?
Number the nodes in the order a depth first search first reaches them. For each node also track
low: the smallest number it can reach by going down the search tree and then following one edge back to a node whose component is still open. A node whoselowequals its own number is the first node of its component.Keep the visited nodes on a stack. When a node finishes with
lowequal to its own number, pop the stack down to that node: those nodes form one component, so count it. One test makes the search 5000 nodes deep, so keep your own stack of (node, next edge) frames instead of recursing.
Solution
Shrink each component to a point and the components form a graph without cycles. Kosaraju's and Tarjan's algorithms use that to find every component in O(n + E), where E is the number of edges.
Search forward and backward from every node
Correct, but does not finish on the largest tests
Intuition
Nodes u and v share a component exactly when each reaches the other. So for a node s with no component yet, search forward along the edges and backward along the reversed edges. The nodes found by both searches are its component. In the first example, forward from 0 finds 0 to 4 and backward finds 0, 1 and 2, so {0, 1, 2} is one component.
Each component costs two searches over most of the graph. On a chain of 5000 edges through 5001 nodes, every node is its own component, and the searches visit about 2.5 × 10^7 nodes.
Algorithm
- Build the outgoing and the incoming edge lists of every node.
- Take the next node
swithout a component and count a new component. - Mark what
sreaches along outgoing edges, and what reaches it along incoming edges. - Every node marked by both searches joins the component of
s. When every node has one, return the count.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countKosaraju's algorithm: two passes
Intuition
In the graph of components some component is a sink, with no edge leaving it, and a search started inside it finds exactly that component. Kosaraju's algorithm orders the searches so each one behaves like that.
The first pass lists every node when its depth first search finishes. The second pass searches the reversed graph, which has the same components, starting from the last node to finish. If an edge leads from component B into C, B's last node finishes after all of C. So when the second pass reaches C, every component with an edge into C is already assigned, and on the reversed graph the search cannot leave C.
In the first example the nodes finish as 4, 3, 2, 1, 0, 5. The second pass collects {5}, then {0, 1, 2}, then {3, 4}.
Algorithm
- Build the outgoing and the incoming edge lists.
- Run an iterative depth first search from every unvisited node, and append each node to
orderwhen it finishes. - Walk
orderfrom the end. For each node without a component, count a new one and search from it along incoming edges, assigning every unassigned node it reaches. Return the count.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countTarjan's algorithm: one pass with low values
Intuition
Run one depth first search and number each node in the order you reach it: its index. Keep a stack of visited nodes whose component is still open, and a value low: the smallest index a node reaches by going down the search tree and then one edge back to a node on that stack.
When a node finishes with low smaller than index, something below it climbs back to an earlier open node, so it stays on the stack. When they are equal, the node is the first one the search entered in its component: pop the stack down to it and count one component. An edge into a popped node leads into a finished component that cannot reach back, so it is ignored.
In the first example, 3 pops {4, 3} and 0 pops {2, 1, 0}. Node 5's edge leads to the popped 4, so 5 pops alone.
Algorithm
- For each unvisited node, give it the next index, set
lowto the same value, push it on the node stack and push the frame (node, first edge). - If the top frame's node has an edge left, follow it: an unvisited target gets an index and a frame, and a target on the node stack lowers
low[node]to its index. - Otherwise pop the frame and lower the parent's
lowtolow[node]. Iflow[node]equalsindex[node], pop the node stack down to the node and count a component.
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
Pitfalls and edge cases
- Forgetting nodes with no edges. In the second example node 4 appears in no edge and is still a component.
- Lowering
lowthrough any visited node instead of only those on the stack. In the first example the edge5 → 4then keeps 5 from closing its component. - Treating the edges as two way. That counts connected components: the first example would give 1 instead of 3.
- Recursing in Python. A cycle through 5000 nodes nests 5000 calls, five times the default limit of 1000. Keep your own stack of frames.
- Running Kosaraju's second pass on the original edges, or in the order the nodes were first visited. Either one merges components that reach each other only one way.
Frequently asked questions3
What is the time complexity of finding strongly connected components?
O(n + E) time with Kosaraju's or Tarjan's algorithm, since every node and edge is handled a constant number of times. Both use O(n + E) space for the edge lists and the search stacks.
Should you use Kosaraju's or Tarjan's algorithm?
Kosaraju's algorithm is two plain searches and harder to get wrong. Tarjan's needs one search and no reversed graph, at the cost of the low bookkeeping.
What is the difference between strongly connected components and connected components?
Connected components ignore edge direction: two nodes are together when some path joins them. Strongly connected components need each node to reach the other. The first example is one connected component but three strongly connected ones.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def countSCC(n, edges):
# Write code hereTest #1
Test #2
Arguments
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
Expected Output
3