Implement the criticalConnectionsBridgeCount method that counts bridge edges in an undirected network.
You are given an undirected connected network as edge pairs. A critical connection, also called a bridge, is an edge whose removal disconnects the network.
Return the number of critical connections.
Example 1
Input
nodes (int) =
4connections (int[][]) =
[[0,1],[1,2],[2,0],[1,3]]size (int) =
4Returns (int)
1Example 2
Input
nodes (int) =
2connections (int[][]) =
[[0,1]]size (int) =
1Returns (int)
1Example 3
Input
nodes (int) =
5connections (int[][]) =
[[1,0],[2,0],[3,2],[4,2],[3,4]]size (int) =
5Returns (int)
2Use Tarjan's bridge-finding algorithm.
During DFS, assign each node a discovery time and compute the lowest discovery time reachable from its subtree using back edges. For an edge from node to child, if low[child] is greater than disc[node], the child cannot reach an ancestor without that edge, so the edge is a bridge.
This finds all bridges in linear time.
Pseudocode:
function criticalConnectionsBridgeCount(nodes, connections, size):
build undirected graph
discovery = array filled with -1
low = array filled with 0
time = 0
bridges = 0
function dfs(node, parent):
discovery[node] = time
low[node] = time
time++
for each next in graph[node]:
if next == parent:
continue
if discovery[next] == -1:
dfs(next, node)
low[node] = min(low[node], low[next])
if low[next] > discovery[node]:
bridges++
else:
low[node] = min(low[node], discovery[next])
dfs(0, -1)
return bridgesReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run