A network of n sites numbered 0 to n - 1 can be built from the possible cables cables[i] = [a, b, cost], which work both ways. There may be several different cheapest networks (sets of cables that connect every site at the lowest total cost).
Write essentialCables(n, cables) that returns, sorted ascending, the indexes of the cables that appear in every cheapest network: removing such a cable from the options would make the cheapest network more expensive, or impossible. The sites can always be connected using all the cables.
Input: n = 4, cables = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,2,3]] Output: [0,1]
The cheapest network costs 4. Without cable 0 or cable 1 it would cost 5. Cables 2 and 3 can replace each other.
Input: n = 3, cables = [[0,1,1],[1,2,1],[0,2,1]] Output: []
Any two of the three equal cables make a cheapest network, so none is in every one.
2 <= n <= 100n - 1 <= cables.length <= 2001 <= cost <= 1000Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #474 Cables in Every Cheapest Network. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.