AAlgoLab
ALG-H020HardGraphs

Critical Network Links

In an undirected graph, return all edges whose removal increases the number of connected components. Represent every bridge as [smaller_node, larger_node] and sort all bridges lexicographically.

Contract

input n: integer
input edges: integer[][]
return integer[][]

Constraints

  • • n >= 1
  • • Undirected graph
  • • No duplicate edges or self-loops
  • • 0 <= node id < n

Examples

Example 1
n = 4
edges = [[0, 1], [1, 2], [2, 0], [1, 3]]
→ [[1, 3]]
Example 2
n = 3
edges = [[0, 1], [1, 2]]
→ [[0, 1], [1, 2]]

5 judge tests (2 shown above). Target complexity: O(V+E).