python 实现求强连通分量

要实现求强连通分量，可以使用深度优先搜索（DFS）算法。以下是一个用 Python 实现的示例代码：

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.Time = 0

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def SCCUtil(self, u, low, disc, stackMember, st):
        disc[u] = self.Time
        low[u] = self.Time
        self.Time += 1
        stackMember[u] = True
        st.append(u)

        for v in self.graph[u]:
            if disc[v] == -1:  # 如果 v 还没被访问过，则递归访问它
                self.SCCUtil(v, low, disc, stackMember, st)
                low[u] = min(low[u], low[v])
            elif stackMember[v] == True:  # 如果 v 在栈中，则更新 low[u]
                low[u] = min(low[u], disc[v])

        w = -1  # 存储强连通分量的顶点
        if low[u] == disc[u]:
            while w != u:
                w = st.pop()
                print(w, end=" ")
                stackMember[w] = False
            print()

    def SCC(self):
        disc = [-1] * (self.V)
        low = [-1] * (self.V)
        stackMember = [False] * (self.V)
        st = []

        for i in range(self.V):
            if disc[i] == -1:
                self.SCCUtil(i, low, disc, stackMember, st)

# 示例用法
g1 = Graph(5)
g1.addEdge(1, 0)
g1.addEdge(0, 2)
g1.addEdge(2, 1)
g1.addEdge(0, 3)
g1.addEdge(3, 4)
print("强连通分量为:")
g1.SCC()

这段代码首先定义了一个 `Graph` 类，其中 `addEdge` 方法用于添加边。`SCCUtil` 方法是实现强连通分量的核心函数。`SCC` 方法用于遍历图中所有的强连通分量并打印出来。

在示例中，我们创建了一个包含 5 个顶点的图，并添加了几条边。然后调用 `SCC` 方法来获取强连通分量。输出结果将显示强连通分量的顶点。