Tarjan 算法实现需要澄清

Question

我一直在研究用于查找网络中关键连接的 Tarjan 算法，特别适用于本 LeetCode 挑战赛中概述的问题。

这是我的代码：

class Solution:
    timer=0
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph=defaultdict(list)
        for a,b in connections:
            graph[a].append(b)
            graph[b].append(a)

        result=[]
        tin=[0]*n
        low=[0]*n
        visited=[False]*n
        def dfs(node,parent):
            self.timer+=1
            visited[node]=True
            tin[node]=self.timer
            low[node]=self.timer
            for child in graph[node]:
                if child==parent: continue
                if visited[child]:
                    low[node]=min(low[node],tin[child])
                else:
                    dfs(child,node)
                    low[node]=min(low[node],low[child])
                    if tin[node]<low[child]:
                        result.append([node,child])
        dfs(0,-1)
        return result

为什么我们不能用条件

if low[node]<low[child]:

代替

if tin[node]<low[child]:

来判断桥是否存在？

我明白，如果我孩子的最低点比我的最低点大，则意味着在我之前永远无法达到它，因此表明有一座桥梁。

Answer 1

对于将来会遇到这个疑问的人。对于这个无向图，

if low[node]<low[child]:

会失败

[[0,1],[1,2],[2,0],[2,3],[1,3]]