使用Tarjan算法在有向图中查找桥梁的特殊情况

Question

我正在尝试更好地了解Tarjan的算法，以查找SCC，发音要点和桥梁。我正在考虑一个特殊情况，该图仅包含2个带有边缘0-＆gt; 1和1-＆gt; 0的节点。以下代码将作为桥梁输出[0,1]。

class Solution(object):
    def criticalConnections(self, n, connections):
        """
        :type n: int
        :type connections: List[List[int]]
        :rtype: List[List[int]]
        """
        g = defaultdict(set)
        pre = [-1]*n
        low = [-1]*n
        cnt = [0]
        for c in connections:
            g[c[0]].add(c[1]) # undirected graph, connect 
            g[c[1]].add(c[0]) # in both directions
        ans = []
        def dfs(edge):            
            v, w = edge
            pre[w] = cnt[0]
            low[w] = pre[w]
            cnt[0] += 1
            for i in g[w]:
                if i == v: continue # we don't want to go back through the same path.
                                    # if we go back is because we found another way back                   
                if pre[i] == -1:
                    dfs((w,i))          
                    # low[i] > pre[w] indicates no back edge to
                    # w's ancesters; otherwise, low[i] will be 
                    # < pre[w]+1 since back edge makes low[i] smaller           
                    if low[i] > pre[w]: 
                    #print(low[i], pre[w]+1, (w,i))                       
                        ans.append([w,i])                
                    low[w] = min(low[w], low[i]) # low[i] might be an ancestor of w
                else: # if i was already discovered means that we found an ancestor
                    low[w] = min(low[w], pre[i]) # finds the ancestor with the least 
                                                 # discovery time
               
                
        dfs((-1,0))
        
        return ans
print(Solution().criticalConnections(2, [[0,1],[1,0]]))

但是，从在线的许多讨论中，删除节点1后，节点0仍可以视为连接（与本身），这意味着边缘0-＆gt; 1不是桥梁。我在这里错过了什么吗？ 还是Tarjan的算法不适合使用2个节点的这种退化图？

Answer 1

有向图中的桥是一条边，删除该边会增加图的强连通分量的数量，以及图无向时的连通分量的数量。因此，当您删除图中的任何边时，强连接组件的数量就会增加，因此在这种情况下该代码的输出是正确的。