1.题目基本信息
1.1.题目描述
力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互连接组成了一个内部集群，连接是无向的。用 connections 表示集群网络，connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。
关键连接 是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。
请你以任意顺序返回该集群内的所有 关键连接 。
1.2.题目地址
https://leetcode.cn/problems/critical-connections-in-a-network/description/
2.解题方法
2.1.解题思路
tarjan计算无向图中桥的个数
2.2.解题步骤
构建tarjan算法的模板，构建图graph，然后获取桥即可，详情请看代码中的注释。
3.解题代码
Python代码
from typing import List
# ==> 无向图的Tarjan算法模板，参数为邻接表，可以获取割点状态、桥、各节点的当前时间戳和子孙节点最小时间戳
class UndirectedGraphTarjan():def __init__(self,graph:List[List[int]]):self.graph=graphself.length=len(self.graph)self.dfn=[-1]*self.length # dfn为各个节点的访问时间戳self.low=[-1]*self.length # low为各个节点的子孙节点中最小时间戳self.cutPoint=[False]*self.length # 各个节点的割点状态self.bridges=[]self.timestamp=0 # 时间戳，初始化为0，且保证唯一# tarjanDfs任务：设置node节点的访问时间戳、子孙节点最小访问时间戳、node的割点状态def tarjanDfs(self,node:int,father:int):# 注意：割点和桥针对无向图，如果图是有向的，则考虑算强连通算法的个数即可（算low中相同的个数即可）# 割点条件：条件1：节点node非root+有儿子，同时dfn(node)<=low(node) / 条件2：节点node是root+非连通儿子节点数大于等于2# 桥的条件：dfn(node)<low(child)# 标记当前节点的访问时间戳并初始化子孙节点中最小的访问时间戳self.dfn[node]=self.timestampself.low[node]=self.timestampself.timestamp+=1childCnt=0for child in self.graph[node]:# 如果子节点等于父节点，跳过，否则反复执行father的dfs任务，造成错误if child!=father:# 如果孩子节点没有访问过if self.dfn[child]==-1:childCnt+=1self.tarjanDfs(child,node) # 设立设置子节点的dfn、low、割点状态# 割点条件1if father!=-1 and self.dfn[node]<=self.low[child] and not self.cutPoint[node]:self.cutPoint[node]=True# 桥的条件if self.dfn[node]<self.low[child]:self.bridges.append([node,child])# 设置node节点的子孙节点中的最小时间戳self.low[node]=min(self.low[node],self.low[child])# 割点条件2if father==-1 and childCnt>=2 and not self.cutPoint[node]:self.low[node]=Trueclass Solution:def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:# 构建图graph=[[] for _ in range(n)]for x,y in connections:graph[x].append(y)graph[y].append(x)# targen算法获取无向图的桥ugTarjan=UndirectedGraphTarjan(graph)ugTarjan.tarjanDfs(0,-1)return ugTarjan.bridges
4.执行结果
