코사라주 알고리즘 편집하기 (부분)

==코드 예제==
<syntaxhighlight lang="python">
from collections import defaultdict

def kosaraju_scc(graph):
    def dfs1(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs1(neighbor)
        stack.append(node)

    def dfs2(node, component):
        visited.add(node)
        component.append(node)
        for neighbor in reversed_graph[node]:
            if neighbor not in visited:
                dfs2(neighbor, component)

    # 1. 첫 번째 DFS 수행하여 스택 채우기
    visited = set()
    stack = []
    for node in graph:
        if node not in visited:
            dfs1(node)

    # 2. 그래프의 모든 간선을 뒤집기
    reversed_graph = defaultdict(list)
    for node in graph:
        for neighbor in graph[node]:
            reversed_graph[neighbor].append(node)

    # 3. 스택에서 꺼낸 순서대로 두 번째 DFS 수행
    visited.clear()
    sccs = []
    while stack:
        node = stack.pop()
        if node not in visited:
            component = []
            dfs2(node, component)
            sccs.append(component)

    return sccs

# 예제 그래프 (방향 그래프)
graph = {
    0: [1],
    1: [2],
    2: [0, 3],
    3: [4],
    4: [5, 6],
    5: [3],
    6: [7],
    7: [8],
    8: [6]
}

# 강한 연결 요소 출력
print(kosaraju_scc(graph))
</syntaxhighlight>
 출력 결과 예시:
 [[6, 8, 7], [3, 5, 4], [0, 2, 1]]
각 리스트는 하나의 SCC를 나타내며, 해당 그룹 내 모든 노드는 서로 도달 가능하다.