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

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=graph
        self.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.timestamp
        self.low[node]=self.timestamp
        self.timestamp+=1
        childCnt=0
        for child in self.graph[node]:
            # 如果子节点等于父节点，跳过，否则反复执行father的dfs任务，造成错误
            if child!=father:
                # 如果孩子节点没有访问过
                if self.dfn[child]==-1:
                    childCnt+=1
                    self.tarjanDfs(child,node)  # 设立设置子节点的dfn、low、割点状态
                    # 割点条件1
                    if 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])
            # 割点条件2
            if father==-1 and childCnt>=2 and not self.cutPoint[node]:
                self.low[node]=True

class 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.执行结果