Essential and Optional Cables
HardAdvanced Graphs
Problem
An engineer has a connected network of n sites and a list of candidate cables cables[i] = [u, v, cost] (undirected; index i identifies the cable). Among all cheapest ways to connect every site, some cables are used by every cheapest plan and some by some but not all of them.
Return [essential, optional]: essential lists the indices of cables present in every minimum-cost plan, and optional lists the indices of cables present in at least one but not all of them. Both lists in ascending order.
Example 1
- Input:
- n = 4, cables = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,2,3]]
- Output:
- [[0,1],[2,3]]
Every cheapest plan (cost 4) uses both cost-1 cables, then either of the two cost-2 cables. The cost-3 cable is never used.
Example 2
- Input:
- n = 3, cables = [[0,1,1],[1,2,1],[0,2,1]]
- Output:
- [[],[0,1,2]]
Any two of the three cables form a cheapest plan.
Example 3
- Input:
- n = 2, cables = [[0,1,5]]
- Output:
- [[0],[]]
Constraints
- 2 ≤ n ≤ 100
- 1 ≤ cables.length ≤ 200
- 1 ≤ cost ≤ 1000
- The cables connect all sites; parallel cables may exist.
Hint
Show the first hint
First compute the minimum total cost W with Kruskal.
Walkthrough
How to approach it
01Clarify before coding
- Is the network guaranteed connected? Yes, so W exists.
- Can a cable be neither? Yes: cables that no cheapest plan uses are in neither list.
- Parallel cables with equal cost? Each is optional, since either one can be chosen.
02Brute force
Enumerate every spanning tree, keep those with minimum cost, and count how often each cable appears.
Cost: The number of spanning trees can be exponential (n^(n-2) for a complete graph).
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.