Lv.3graphofflineunion-find
Connectivity Under Road Closures
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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]: roadecloses (and never reopens).[2, a, b]: can you currently travel fromatobusing open roads only?
Return the answers of the 2 commands (true/false) in order.
Examples
| n | roads | ops | result |
|---|---|---|---|
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
-
n,roads.length; parallel roads anda = bmay appear -
ops.length [1, e]:e, no road is closed twice;[2, a, b]:a,b- At least one
2command exists.
Expected complexity
- Time
- O((N + M + Q) α(N))
- Space
- O(N + M + Q)
Examples
| n | roads | ops | Expected |
|---|---|---|---|
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 and exceeds the time
limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 360 ms | estimated |
| C++ (GCC, gnu++23) | 360 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1928 ms | derived |
| Kotlin 2.4 (JVM) | 1720 ms | estimated |
| C# 14 (.NET 10) | 1720 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |