tarjan算法python实现

Tarjan算法是一种常见的图论算法，用于寻找有向图中的强连通分量。以下是Python实现：

class Tarjan:
    def __init__(self, graph):
        self.graph = graph
        self.index = 0
        self.stack = []
        self.ids = [-1] * len(graph)
        self.low_links = [-1] * len(graph)
        self.on_stack = [False] * len(graph)
        self.sccs = []

        for i in range(len(graph)):
            if self.ids[i] == -1:
                self._dfs(i)

    def _dfs(self, node):
        self.stack.append(node)
        self.ids[node] = self.index
        self.low_links[node] = self.index
        self.index += 1
        self.on_stack[node] = True

        for neighbor in self.graph[node]:
            if self.ids[neighbor] == -1:
                self._dfs(neighbor)
                self.low_links[node] = min(self.low_links[node], self.low_links[neighbor])
            elif self.on_stack[neighbor]:
                self.low_links[node] = min(self.low_links[node], self.ids[neighbor])

        if self.ids[node] == self.low_links[node]:
            scc = []
            while True:
                n = self.stack.pop()
                self.on_stack[n] = False
                scc.append(n)
                if n == node:
                    break
            self.sccs.append(scc)

其中，`graph`是一个邻接表，表示有向图中每个节点的邻居。`ids`和`low_links`是每个节点的DFS编号和最小的可以到达的祖先节点的DFS编号。`on_stack`表示当前节点是否在栈中，`stack`表示DFS过程中遍历到的所有节点。`sccs`表示找到的所有强连通分量。在构造函数中，对于每个没有被访问过的节点，调用`_dfs`函数进行遍历，如果找到了一个强连通分量，就将其中的节点弹出栈并记录下来。