A strongly connected component contains vertices that can each reach every other vertex through directed paths.
Python strongly connected components: partition a directed dependency graph
Operation contract
The bounded graph fixture computes finishing order on the original adjacency and then explores reversed edges in reverse finishing order. Each second-pass traversal owns one component. Isolated vertices are included. Sorting component members and the final component list gives a stable teaching result without changing the graph-theoretic partition.
Failure and ownership boundary
A directed path in only one direction does not make two vertices strongly connected. Cycles can be represented as one component before building a component-level acyclic dependency graph. Duplicate edges and self-loops are accepted here; invalid endpoints are rejected before traversal. Python topological sort: dependency order and cycle rejection and Python graph BFS: mark a vertex when it enters the queue concern related but different outputs.
Working program
def dependency_components(count, edges):
if type(count) is not int or not 0 <= count <= 32 or len(edges) > 256:
raise ValueError("graph budget rejected")
forward, backward = [[] for _ in range(count)], [[] for _ in range(count)]
for edge in edges:
if not isinstance(edge, tuple) or len(edge) != 2 or any(type(node) is not int or not 0 <= node < count for node in edge):
raise ValueError("edge rejected")
source, target = edge
forward[source].append(target); backward[target].append(source)
seen = set(); finished = []
def finish(node):
seen.add(node)
for neighbor in forward[node]:
if neighbor not in seen: finish(neighbor)
finished.append(node)
for node in range(count):
if node not in seen: finish(node)
seen.clear(); components = []
def collect(node, component):
seen.add(node); component.append(node)
for neighbor in backward[node]:
if neighbor not in seen: collect(neighbor, component)
for node in reversed(finished):
if node not in seen:
component = []; collect(node, component); components.append(sorted(component))
return sorted(components)
print(dependency_components(6, [(0,1),(1,2),(2,0),(2,3),(3,4),(4,3)]))
print(dependency_components(2, [(0,1)]))Output
[[0, 1, 2], [3, 4], [5]]
[[0], [1]]Costs and limits
The two traversals and reversed adjacency use O(V+E) graph work and storage before output sorting. Recursive depth is bounded by at most 32 accepted vertices here; a larger graph needs a stack policy rather than blindly raising the interpreter recursion limit.
Common Mistakes
- Use reversed edges for the second traversal.
- Include isolated vertices rather than deriving vertices only from edges.
Connected lessons
Python topological sort: dependency order and cycle rejection, Python graph BFS: mark a vertex when it enters the queue, Python recursion: bound depth instead of raising the limit.
Follow the service contract
Python graph condensation: collapse directed cycles into an acyclic component graph.
