Funcia
Lv.3graphofflineunion-find

Connectivity Under Road Closures

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

There are n villages numbered 0 to n - 1 and two-way roads roads, where roads[e] = [a, b] is road e between villages a and b. Initially every road is open. Process the commands ops in order:

  • [1, e]: road e closes (and never reopens).
  • [2, a, b]: can you currently travel from a to b using open roads only?

Return the answers of the 2 commands (true/false) in order.

Examples

nroadsopsresult
4[[0, 1], [1, 2], [2, 3], [0, 3]][[2, 0, 2], [1, 1], [2, 0, 2], [1, 3], [2, 0, 2], [2, 2, 3]][true, true, false, true]
3[[0, 1]][[2, 1, 1], [2, 0, 2], [1, 0], [2, 0, 1]][true, false, false]

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[][], ops: int[][]) → bool[]

Constraints

  • 1≤1 \le n ≤200,000\le 200{,}000, 0≤M=0 \le M = roads.length ≤200,000\le 200{,}000; parallel roads and a = b may appear
  • 1≤Q=1 \le Q = ops.length ≤200,000\le 200{,}000
  • [1, e]: 0≤0 \le e <M< M, no road is closed twice; [2, a, b]: 0≤0 \le a, b <n< n
  • At least one 2 command exists.

Expected complexity

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

Examples

nroadsopsExpected
4[[0,1],[1,2],[2,3],[0,3]][[2,0,2],[1,1],[2,0,2],[1,3],[2,0,2],[2,2,3]][true,true,false,true]
3[[0,1]][[2,1,1],[2,0,2],[1,0],[2,0,1]][true,false,false]

Hint

Hint

Union-find can merge but not split, so process the commands backwards: start from the final state (only roads that are never closed are open), treat each [1, e] as the road reopening (union), and answer each [2, a, b] with find(a) == find(b); reverse the recorded answers at the end. A BFS per query is O(Q⋅(N+M))O(Q \cdot (N + M)) and exceeds the time limit.

Time limits per language

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

Test groups

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

No result yet. Run or submit your code.