Here is the bridge-finding implementation:
function criticalConnections(n, adj):
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])
for i from 0 to n - 1:
if disc[i] == -1:
dfs(i, -1)
return bridges
Time: . Space: .