Funktionen der Software · Stark verbundene gerichtete Komponenten

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)