Convoy Reachable Towns
Hard · union find
A region has n towns, numbered 0 to n - 1, joined by two-way roads. Each entry of roads is [a, b, width]: a road between towns a and b that is width metres wide. Two towns can be joined by more than one road, and no road joins a town to itself.
A convoy of lorries of a given width can only drive along roads that are at least as wide as the convoy. It may pass through towns and turn round as often as it likes.
Each query is [town, w] and asks: starting in town, with a convoy w metres wide, how many towns can the convoy reach? The start town counts, so the answer is always at least 1.
Return a list with one answer per query, in the same order as queries.
Examples
Example 1
Input: n = 6, roads = [[0, 1, 6], [1, 2, 7], [2, 3, 2], [3, 4, 9], [1, 3, 5]], queries = [[0, 1], [0, 6], [0, 8], [3, 9], [5, 1]]
Output: [5, 3, 1, 2, 1]
Width 1 fits every road, so town 0 reaches towns 0 to 4. Width 6 keeps only the roads 0-1, 1-2 and 3-4, so town 0 reaches 0, 1 and 2. Width 8 keeps only 3-4, which does not touch town 0. Town 5 has no roads at all.
Example 2
Input: n = 3, roads = [[0, 1, 5]], queries = [[1, 5], [1, 6], [2, 1]]
Output: [2, 1, 1]
A road of width 5 is wide enough for a convoy of width 5, but not for width 6.
Constraints
- 1 <= n <= 10^5
- 0 <= len(roads) <= 2 * 10^5
- roads[i] = [a, b, width] with 0 <= a, b < n and a != b
- 1 <= width <= 10^9
- 1 <= len(queries) <= 10^5
- queries[i] = [town, w] with 0 <= town < n and 1 <= w <= 10^9