Strongly Connected Parts
Graphs: lesson 16 of 16
Groups where every node can reach every other — found in two passes.
Lesson 16 of 16 · 7 min
Strongly Connected Parts
Step 1 of 16
Five services, all one-way calls. a, b, c ring each other; d, e ring each other. The list of calls does not say so.
The Idea
In a directed graph, mutual reachability splits the nodes into groups. Kosaraju finds them twice over: one DFS records the order nodes finish in, then every edge is reversed and a second DFS starts from the last finisher. Reversal keeps each group intact but cuts the one-way roads between groups, so each restart collects exactly one component.
Real-World Example
A dependency audit of microservices. Services that call each other in a ring must deploy together and fail together, and the ring is invisible in a list of calls. Grouping them names the blast radius before an incident does.
The Code
g = {"a": ["b"], "b": ["c"], "c": ["a", "d"], "d": ["e"], "e": ["d"]}
order, seen = [], set()
def walk(n):
seen.add(n)
for m in g[n]:
if m not in seen:
walk(m)
order.append(n) # finished last, so it starts the next pass
for n in g:
if n not in seen:
walk(n)
rev = {n: [] for n in g}
for n in g:
for m in g[n]:
rev[m].append(n) # every arrow turned around
seen, groups = set(), []
def collect(n, group):
seen.add(n)
group.append(n)
for m in rev[n]:
if m not in seen:
collect(m, group)
for n in reversed(order):
if n not in seen:
group = []
collect(n, group)
groups.append(sorted(group))
print(groups) # [['a', 'b', 'c'], ['d', 'e']]Your turn
What does this print?
g = {"x": ["y"], "y": ["x"], "z": ["x"]}
rev = {n: [] for n in g}
for n in g:
for m in g[n]:
rev[m].append(n)
print(rev)Mini quiz
1 / 3