sites nodes numbered from 0 to sites - 1. The possible cables are given in cables: cables[i] = [a, b, cost] is a cable between nodes a and b that costs cost. Laying all the cables would connect every node.
A *cheapest network* is a set of cables that connects all nodes (any node can reach any other) at the smallest possible total cost. There may be several of them.
Split the cables into two kinds:
- *required*: part of every cheapest network (without such a cable the cheapest network gets more expensive or impossible);
- *spare*: part of some cheapest networks, but not all of them.
Return [required, spare], two lists of cable indices. Cables that belong to no cheapest network go in neither list. Indices inside each list may come in any order.sites=4, cables=[[0, 1, 2], [1, 2, 3], [0, 2, 3], [2, 3, 1]] → [[3, 0], [1, 2]]
The cheapest network costs 6: cables 0 and 3 plus either cable 1 or cable 2 (both cost 3). Cables 0 and 3 are always needed, while 1 and 2 can replace each other.
sites=3, cables=[[0, 1, 5], [1, 2, 5], [0, 2, 9]] → [[0, 1], []]
The only cheapest network is cables 0 and 1 for 10. Cable 2 is not part of any cheapest network.
sites=3, cables=[[0, 1, 4], [1, 2, 4], [0, 2, 4]] → [[], [0, 1, 2]]
sites=4, cables=[[0, 1, 2], [1, 2, 3], [0, 2, 3], [2, 3, 1]]
[[3, 0], [1, 2]]
Run checks the first 3 tests in your browser. Submit checks all 55 tests on the server, hidden ones included.