Tarjan算法求割点与割边(python3实现)

from typing import List, Tuple


'''
Trajan算法求无向图的桥
'''

class Tarjan:
    # 求无向连通图的桥
    @staticmethod
    def getCuttingPointAndCuttingEdge(edges: List[Tuple]):
        link, dfn, low = {}, {}, {}# link为字典邻接表
        global_time = [0]
        for a, b in edges:
            if a not in link:
                link[a] = []
            if b not in link:
                link[b] = []
            link[a].append(b)#无向图
            link[b].append(a)#无向图
            dfn[a], dfn[b] = 0x7fffffff, 0x7fffffff
            low[a], low[b] = 0x7fffffff, 0x7fffffff


        cutting_points, cutting_edges = [], []

        def dfs(cur, prev, root):
            global_time[0] += 1
            dfn[cur], low[cur] = global_time[0], global_time[0]

            children_cnt = 0
            flag = False
            for next in link[cur]:
                if next != prev:
                    if dfn[next] == 0x7fffffff:
                        children_cnt += 1
                        dfs(next, cur, root)

                        if cur != root and low[next] >= dfn[cur]:
                            flag = True
                        low[cur] = min(low[cur], low[next])

                        if low[next] > dfn[cur]:
                            cutting_edges.append([cur, next] if cur < next else [next, cur])
                    else:
                        low[cur] = min(low[cur], dfn[next])

            if flag or (cur == root and children_cnt >= 2):
                cutting_points.append(cur)

        dfs(edges[0][0], None, edges[0][0])
        return cutting_points, cutting_edges


class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        edges = [(a, b) for a, b in connections]
        cutting_dots, cutting_edges = Tarjan.getCuttingPointAndCuttingEdge(edges)
        return [[a, b] for a, b in cutting_edges]


connections = [[0,1],[1,2],[2,0],[1,3]]
n = 4
s = Solution()
result = s.criticalConnections(n,connections)
print(result)      

​​1192. 查找集群内的「关键连接」​​

难度困难39

力扣数据中心有 ​

​n​

​​ 台服务器，分别按从 ​

​0​

​​ 到 ​

​n-1​

​ 的方式进行了编号。

它们之间以「服务器到服务器」点对点的形式相互连接组成了一个内部集群，其中连接 ​

​connections​

​ 是无向的。

从形式上讲，​

​connections[i] = [a, b]​

​​ 表示服务器 ​

​a​

​​ 和 ​

​b​

​ 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。

「关键连接」是在该集群中的重要连接，也就是说，假如我们将它移除，便会导致某些服务器无法访问其他服务器。

请你以任意顺序返回该集群内的所有 「关键连接」。

示例 1：

输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

输出：[[1,3]]

解释：[[3,1]] 也是正确的。

• ​

  ​1 <= n <= 10^5​

  ​
• ​

  ​n-1 <= connections.length <= 10^5​

  ​
• ​

  ​connections[i][0] != connections[i][1]​

  ​
• 不存在重复的连接