Leetcode 1192. 查找集群内的关键毗连

1.标题根本信息

1.1.标题描述

力扣数据中央有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互毗连构成了一个内部集群，毗连是无向的。用 connections 表示集群网络，connections = [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代码

1. from typing import List
2. # ==> 无向图的Tarjan算法模板，参数为邻接表，可以获取割点状态、桥、各节点的当前时间戳和子孙节点最小时间戳
3. class UndirectedGraphTarjan():
4.     def __init__(self,graph:List[List[int]]):
5.         self.graph=graph
6.         self.length=len(self.graph)
7.         self.dfn=[-1]*self.length   # dfn为各个节点的访问时间戳
8.         self.low=[-1]*self.length   # low为各个节点的子孙节点中最小时间戳
9.         self.cutPoint=[False]*self.length   # 各个节点的割点状态
10.         self.bridges=[]
11.         self.timestamp=0    # 时间戳，初始化为0，且保证唯一
12.    
13.     # tarjanDfs任务：设置node节点的访问时间戳、子孙节点最小访问时间戳、node的割点状态
14.     def tarjanDfs(self,node:int,father:int):
15.         # 注意：割点和桥针对无向图，如果图是有向的，则考虑算强连通算法的个数即可（算low中相同的个数即可）
16.         # 割点条件：条件1：节点node非root+有儿子，同时dfn(node)<=low(node) / 条件2：节点node是root+非连通儿子节点数大于等于2
17.         # 桥的条件：dfn(node)<low(child)
18.         # 标记当前节点的访问时间戳并初始化子孙节点中最小的访问时间戳
19.         self.dfn[node]=self.timestamp
20.         self.low[node]=self.timestamp
21.         self.timestamp+=1
22.         childCnt=0
23.         for child in self.graph[node]:
24.             # 如果子节点等于父节点，跳过，否则反复执行father的dfs任务，造成错误
25.             if child!=father:
26.                 # 如果孩子节点没有访问过
27.                 if self.dfn[child]==-1:
28.                     childCnt+=1
29.                     self.tarjanDfs(child,node)  # 设立设置子节点的dfn、low、割点状态
30.                     # 割点条件1
31.                     if father!=-1 and self.dfn[node]<=self.low[child] and not self.cutPoint[node]:
32.                         self.cutPoint[node]=True
33.                     # 桥的条件
34.                     if self.dfn[node]<self.low[child]:
35.                         self.bridges.append([node,child])
36.                 # 设置node节点的子孙节点中的最小时间戳
37.                 self.low[node]=min(self.low[node],self.low[child])
38.             # 割点条件2
39.             if father==-1 and childCnt>=2 and not self.cutPoint[node]:
40.                 self.low[node]=True
42. class Solution:
43.     def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
44.         # 构建图
45.         graph=[[] for _ in range(n)]
46.         for x,y in connections:
47.             graph[x].append(y)
48.             graph[y].append(x)
49.         # targen算法获取无向图的桥
50.         ugTarjan=UndirectedGraphTarjan(graph)
51.         ugTarjan.tarjanDfs(0,-1)
52.         return ugTarjan.bridges

复制代码

4.实行结果

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。