用 20 行代码借助 Tarjan 算法求解强连通分量

在图论中，强连通分量是一个非常重要的概念。强连通分量是指在有向图中，一个最大的子图，其中任意两个顶点之间都存在路径。求解强连通分量在很多领域都有广泛的应用，比如网络分析、程序优化等。

Tarjan 算法是一种高效的求解强连通分量的算法。下面我们将展示如何用 20 行代码来实现 Tarjan 算法求解强连通分量。

我们需要定义一些数据结构来存储图的信息。我们可以使用邻接表来表示图。

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u].append(v)

接下来，我们实现 Tarjan 算法的核心部分。

index = 0
low = [0] * num_vertices
on_stack = [False] * num_vertices
stack = []
scc_count = 0
scc_ids = [0] * num_vertices

def tarjan_scc(graph, vertex):
    global index, scc_count
    index += 1
    low[vertex] = index
    stack.append(vertex)
    on_stack[vertex] = True

    for neighbor in graph.adj[vertex]:
        if low[neighbor] == 0:
            tarjan_scc(graph, neighbor)
            low[vertex] = min(low[vertex], low[neighbor])
        elif on_stack[neighbor]:
            low[vertex] = min(low[vertex], low[neighbor])

    if low[vertex] == index:
        scc_count += 1
        while stack[-1]!= vertex:
            node = stack.pop()
            on_stack[node] = False
            scc_ids[node] = scc_count
        stack.pop()
        on_stack[vertex] = False
        scc_ids[vertex] = scc_count

最后，我们可以使用以下代码来调用 Tarjan 算法并输出强连通分量的结果。

graph = Graph(5)
graph.add_edge(0, 1)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(1, 3)
graph.add_edge(3, 4)

for vertex in range(graph.V):
    if low[vertex] == 0:
        tarjan_scc(graph, vertex)

print("强连通分量个数:", scc_count)
for vertex in range(graph.V):
    print("顶点", vertex, "属于强连通分量", scc_ids[vertex])

通过这 20 行左右的代码，我们成功地利用 Tarjan 算法求解了强连通分量。希望这个简单的示例能够帮助您理解和应用 Tarjan 算法来解决相关问题。