编辑“︁强连通分量”︁（章节）

== 算法实现 ==
常用算法包括 Kosaraju 算法和 Tarjan 算法。以下以 Kosaraju 算法为例：

=== Kosaraju 算法步骤 ===
1. '''第一次 DFS'''：对原图 <math>G</math> 进行深度优先搜索，按完成时间逆序记录顶点。
2. '''反转图'''：构造 <math>G</math> 的转置图 <math>G^T</math>（所有边反向）。
3. '''第二次 DFS'''：按逆序在 <math>G^T</math> 上 DFS，每棵树对应一个 SCC。

=== 代码示例 ===
<syntaxhighlight lang="python">
from collections import defaultdict

def kosaraju(graph):
    visited = set()
    order = []
    
    # 第一次DFS生成逆序
    def dfs(u):
        stack = [(u, False)]
        while stack:
            node, processed = stack.pop()
            if processed:
                order.append(node)
                continue
            if node in visited:
                continue
            visited.add(node)
            stack.append((node, True))
            for v in graph[node]:
                if v not in visited:
                    stack.append((v, False))
    
    for u in graph:
        if u not in visited:
            dfs(u)
    
    # 构造转置图
    transposed = defaultdict(list)
    for u in graph:
        for v in graph[u]:
            transposed[v].append(u)
    
    # 第二次DFS找SCC
    visited.clear()
    sccs = []
    for u in reversed(order):
        if u not in visited:
            stack = [u]
            visited.add(u)
            component = []
            while stack:
                node = stack.pop()
                component.append(node)
                for v in transposed[node]:
                    if v not in visited:
                        visited.add(v)
                        stack.append(v)
            sccs.append(component)
    return sccs

# 示例输入
graph = {
    0: [1],
    1: [2],
    2: [0, 3],
    3: [4],
    4: [5],
    5: [3]
}
print(kosaraju(graph))  # 输出: [[0, 2, 1], [3, 5, 4]]
</syntaxhighlight>

=== 输入输出说明 ===
* 输入：有向图的邻接表表示。
* 输出：强连通分量列表，每个分量是顶点的集合。示例中 SCC 为 <math>\{0,1,2\}</math> 和 <math>\{3,4,5\}</math>。