Storm Road Closures
Hard · union find
A mountain region has n villages, numbered 0 to n - 1, and a list roads of two-way roads. Road number i is roads[i] = [a, b], a road between villages a and b. Roads are numbered from 0 in the order of the list, and two villages may be joined by more than one road.
During a storm the council closes roads one at a time. The list closures gives the road numbers in the order they are closed. No road is closed twice, and not every road has to be closed. A closed road stays closed.
You are also given a list of queries. Each query is [t, a, b] and asks: after exactly the first t closures in closures have happened, can someone walk from village a to village b using only roads that are still open? They may pass through other villages. A village can always reach itself.
Return a list with one answer per query, in the same order as queries: true if the walk is possible, false if not.
Examples
Example 1
Input: n = 5, roads = [[0, 1], [1, 2], [2, 3], [3, 4], [0, 4]], closures = [0, 2], queries = [[0, 0, 2], [1, 0, 2], [2, 0, 2], [2, 1, 3], [2, 0, 4]]
Output: [true, true, false, false, true]
The roads form a ring. After closing road 0 (between 0 and 1) you can still go 0, 4, 3, 2. After closing road 2 as well, villages 1 and 2 are cut off from 0, 3 and 4.
Example 2
Input: n = 3, roads = [[0, 1], [1, 2]], closures = [1, 0], queries = [[2, 0, 1], [1, 0, 1], [0, 0, 2], [2, 2, 2]]
Output: [false, true, true, true]
After both closures no road is left, so 0 cannot reach 1. After only road 1 is closed, 0 still reaches 1. Village 2 always reaches itself.
Example 3
Input: n = 2, roads = [], closures = [], queries = [[0, 0, 1]]
Output: [false]
There are no roads at all.
Constraints
- 1 <= n <= 10^5
- 0 <= len(roads) <= 10^5
- roads[i] has exactly two village numbers, 0 <= a, b < n and a != b
- closures holds distinct road numbers, each from 0 to len(roads) - 1
- 0 <= len(queries) <= 10^5
- queries[i] has exactly three numbers: t, a and b
- 0 <= t <= len(closures)
- 0 <= a, b < n (a may equal b)