I am trying to get better understanding of Tarjan's algorithm for finding SCC, articulation points and bridges. I am considering a special case where the graph contains only 2 nodes with edges 0->1 and 1->0. The following code will output [0,1] as a bridge.
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]]))
However, from many discussions online, after removing node 1, node 0 can still be considered as connected (to itself) which means edge 0->1 is not a bridge. Am I missing something here? Or Tarjan's algorithm is not suitable for this kind of degenerate graph with 2 nodes?
You comments are welcome.
Thanks
CodePudding user response:
A bridge in a directed graph is an edge whose deletion increases the graph's number of strongly connected components. And when you remove any edge in your graph then the number of strongly connected components increases so the output of this code is correct in this case.