python获取无向图的双连通分量

要获取无向图的双连通分量，可以使用Tarjan算法。以下是一个Python实现的示例代码：

def tarjan_biconnected_components(graph):
    """
    Tarjan算法计算无向图的双连通分量
    :param graph: 无向图，用邻接列表表示
    :return: 双连通分量列表
    """
    index_counter = [0]
    stack = []
    lowlink = {}
    index = {}
    result = []
    bridges = []

    def strongconnect(node):
        # 为节点赋予唯一的索引
        index[node] = index_counter[0]
        lowlink[node] = index_counter[0]
        index_counter[0] += 1
        stack.append(node)

        # 对于每个相邻节点v
        for v in graph[node]:
            # 如果v没有被访问过，则递归调用strongconnect
            if v not in index:
                strongconnect(v)
                lowlink[node] = min(lowlink[node], lowlink[v])
                # 如果v是一个桥，则将桥添加到bridges列表中
                if lowlink[v] == index[v]:
                    bridges.append((node, v))
            # 如果v已经在堆栈中，则更新此节点的lowlink
            elif v in stack:
                lowlink[node] = min(lowlink[node], index[v])

        # 如果节点是一个连接分量的根，则弹出堆栈，并收集连通分量
        if lowlink[node] == index[node]:
            connected_component = []
            while True:
                v = stack.pop()
                connected_component.append(v)
                if v == node:
                    break
            result.append(connected_component)

    for node in graph:
        if node not in index:
            strongconnect(node)

    return result

使用示例：

graph = {
    1: {2, 3},
    2: {1, 3, 4},
    3: {1, 2, 4},
    4: {2, 3, 5},
    5: {4}
}

result = tarjan_biconnected_components(graph)
print(result)  # 输出：[[1, 2, 3], [4, 5]]

以上代码实现了Tarjan算法，用于计算无向图的双连通分量。传入的图以邻接列表表示，返回的结果是双连通分量的列表。对于结果中的每个双连通分量，其包含的节点组成了一个强连通分量，即任意两个节点都有一条路径相连。