Critical Connections in a Network

Given an undirected connected network, return all critical connections (bridges). A bridge is an edge whose removal increases the number of connected components. Pattern focus: Bridges. Use DFS entry times and low-link values to detect edges that are the only route between two parts of the graph.

Input Format

n = number of vertices, connections = undirected edges [u, v]

Output Format

all bridges, each edge sorted ascending and bridges sorted lexicographically

Constraints

  • 1 <= n <= 10^5
  • 1 <= connections.length <= 2 * 10^5

Examples

Example 1:

Input:

n = 4
connections = [[1,2],[2,3],[3,1],[3,4]]

Output:

[[3,4]]

Explanation:

Only edge (3,4) is a bridge.

Example 2:

Input:

n = 5
connections = [[1,2],[1,3],[3,4],[3,5],[4,5]]

Output:

[[1,2],[1,3]]

Explanation:

Removing either edge from vertex 1 disconnects a leaf-like part.

Example 3:

Input:

n = 6
connections = [[1,2],[2,3],[3,1],[3,4],[4,5],[5,6]]

Output:

[[3,4],[4,5],[5,6]]

Explanation:

The tail edges are all bridges.

Loading...
Critical Connections in a Network