Skip to content
AITroveRead. Build. Understand.
Make this comfortable

Python strongly connected components: partition a directed dependency graph

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

A strongly connected component contains vertices that can each reach every other vertex through directed paths.

Download Python source kit

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

python
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

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.

python
strongly-connected-components
Storage details