All problems

Find Critical and Pseudo-Critical Edges

Hard · minimum spanning tree

A telephone company has n exchanges, numbered 0 to n - 1. The list links holds the cables it could lay. Each entry [a, b, cost] is a two-way cable between exchanges a and b that costs cost to lay. The cable at position i in the list is called cable i, counting from 0.

A network is a set of cables that lets every exchange reach every other, directly or through other exchanges. A network is cheapest if no other network has a smaller total cost. There may be many cheapest networks.

• A cable is essential if it belongs to every cheapest network.
• A cable is flexible if it belongs to some cheapest networks, but not all of them.

Return two lists in one list, [essential, flexible]: the numbers of the essential cables and the numbers of the flexible cables, each in ascending order. A cable that belongs to no cheapest network is in neither list. A list with no cables is written [].

The cables connect all the exchanges, so a network always exists. Several cables may join the same pair of exchanges, and no cable joins an exchange to itself.

Examples

Example 1

Input: n = 4, links = [[0, 1, 1], [1, 2, 1], [0, 2, 1], [2, 3, 5]]

Output: [[3], [0, 1, 2]]

Cable 3 is the only way to reach exchange 3, so it is essential. The three cables of cost 1 form a triangle, and any two of them do the job, so each is flexible.

Example 2

Input: n = 3, links = [[0, 1, 1], [1, 2, 2], [0, 2, 3]]

Output: [[0, 1], []]

The only cheapest network is cables 0 and 1. Cable 2 is never needed.

Example 3

Input: n = 2, links = [[0, 1, 4], [0, 1, 4], [0, 1, 7]]

Output: [[], [0, 1]]

Either cost-4 cable alone is a cheapest network, so both are flexible and neither is essential. The cost-7 cable is never needed.

Constraints

• 2 <= n <= 100
• n - 1 <= len(links) <= 200
• Each link is [a, b, cost] with 0 <= a, b < n, a != b and 1 <= cost <= 1000.
• The cables connect all the exchanges.