Open the context
Choose the project folder and name the files or behavior involved.
Workflows
Coding workflows · Directed strongly connected components
03
A concrete starting point
Partition a directed graph of at most 64 vertices into strongly connected components. Test cycles, isolated vertices and empty input, rejecting invalid set members without changing the adjacency sets.
Define the change
Describe the input, expected output and boundaries that must stay intact.
Inspect the work
Review the proposed edits and any commands before relying on their result.
Check the outcome
Compare actual behavior with the expected result. If a check fails, investigate it before applying more changes.
Directed strongly connected components
A concrete starting point
def strong_components(graph):
if type(graph) is not list or len(graph) > 64:
raise ValueError("scc.graph")
n = len(graph)
if any(type(row) is not set or any(type(v) is not int or not 0 <= v < n for v in row) for row in graph):
raise ValueError("scc.edge")
seen, order = set(), []
for start in range(n):
if start in seen:
continue
seen.add(start)
stack = [(start, iter(sorted(graph[start])))]
while stack:
node, edges = stack[-1]
target = next(edges, None)
if target is None:
order.append(node)
stack.pop()
elif target not in seen:
seen.add(target)
stack.append((target, iter(sorted(graph[target]))))
reverse = [set() for _ in graph]
for node, edges in enumerate(graph):
for target in edges:
reverse[target].add(node)
seen, result = set(), []
for start in reversed(order):
if start in seen:
continue
group, pending = [], [start]
seen.add(start)
while pending:
node = pending.pop()
group.append(node)
for target in reverse[node]-seen:
seen.add(target)
pending.append(target)
result.append(sorted(group))
return sorted(result)
The example is a starting point for a real project, not a claim that generated code is already tested. Adjust paths, dependencies and expected behavior to match your application.