Two Fleets, One Road Network
HardGraphs
Problem
A city has n junctions numbered 0 to n - 1 and two delivery fleets, A and B. Each entry [type, a, b] of roads is a two-way road between junctions a and b: type 1 roads may be used only by fleet A, type 2 only by fleet B, and type 3 by both.
The city wants to close as many roads as possible while each fleet can still travel between every pair of junctions using the roads it is allowed on. Return the maximum number of roads that can be closed, or -1 if one of the fleets cannot already reach every junction.
Example 1
- Input:
- n = 4, roads = [[3, 0, 1], [3, 1, 2], [1, 0, 2], [1, 1, 3], [1, 2, 3], [2, 2, 3]]
- Output:
- 2
Keep both shared roads, A-road [1, 3] and B-road [2, 3]. A-roads [0, 2] and [2, 3] are redundant.
Example 2
- Input:
- n = 4, roads = [[3, 1, 2], [3, 2, 3], [1, 0, 3], [2, 0, 1]]
- Output:
- 0
Every road is needed by some fleet.
Example 3
- Input:
- n = 4, roads = [[3, 1, 2], [3, 2, 3], [1, 0, 3]]
- Output:
- -1
Fleet B can never reach junction 0.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ roads.length ≤ 10^5
- type ∈ {1, 2, 3}
- 0 ≤ a, b < n, a ≠ b
Hint
Show the first hint
Minimising the roads you keep is the same as maximising the roads you close. Which roads are the most valuable to keep?
Walkthrough
How to approach it
01Clarify before coding
- Does a shared road count once or twice when kept? Once: it is one road.
- If a fleet is already disconnected, what is returned? -1.
- Can there be duplicate roads? Yes; duplicates are simply closable.
02Brute force
Try every subset of roads to keep, check both fleets' connectivity, and keep the smallest valid subset.
Cost: O(2^R · (n + R)): impossible for more than about 20 roads.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.