Here is the bridge-finding implementation:
function criticalConnections(n, edges):
adj = build adjacency list from edges
disc = array of size n, all -1
low = array of size n, all -1
bridges = empty list
timer = 0
function dfs(u, parent):
disc[u] = timer
low[u] = timer
timer = timer + 1
for v in adj[u]:
if v == parent:
continue
if disc[v] == -1:
dfs(v, u)
low[u] = min(low[u], low[v])
if low[v] > disc[u]:
bridges.append((u, v))
else:
low[u] = min(low[u], disc[v])
dfs(0, -1)
return bridges
Time: . Space: .