Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
Guru Level

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) = 4
connections (int[][]) = [[0,1],[1,2],[2,0],[1,3]]
size (int) = 4
Return:
(int) 1
Example 2
Input:
nodes (int) = 2
connections (int[][]) = [[0,1]]
size (int) = 1
Return:
(int) 1
Example 3
Input:
nodes (int) = 5
connections (int[][]) = [[1,0],[2,0],[3,2],[4,2],[3,4]]
size (int) = 5
Return:
(int) 2

Use 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 bridges
Run your code to see the result.