Funcia
Lv.4bridgesdfsgraph

Critical Roads (Bridges)

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Road i is roads[i] = [a, b] (two-way). A road is critical if removing it disconnects two cities that were connected. Return the indices of the critical roads in increasing order. Parallel roads protect each other.

Examples

nroadsresult
5[[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]][3, 4]
2[[0, 1], [1, 0]][]
4[[0, 1], [2, 3]][0, 1]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(n: int, roads: int[][]) → int[]

Constraints

  • 1≤1 \le n ≤100,000\le 100{,}000, 0≤0 \le roads.length ≤200,000\le 200{,}000
  • a≠ba \ne b; parallel roads may appear.

Expected complexity

Time
O(N + M)
Space
O(N + M)

Examples

nroadsExpected
5[[0,1],[1,2],[2,0],[1,3],[3,4]][3,4]
2[[0,1],[1,0]][]
4[[0,1],[2,3]][0,1]

Hint

Hint

Tarjan's bridge finding: a tree edge u → v is a bridge iff low[v] > tin[u]. Skip the parent by edge index (parallel roads), and use an iterative DFS for deep graphs. Removing each road and re-checking connectivity is O(M(N+M))O(M(N + M)).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251738 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness408verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.