775. Critical MST Edges
An island has n harbours numbered 0 to n - 1. Each entry [a, b, w] of edges is a possible two-way bridge of cost w between harbours a and b; its identifier is its position in the array. The harbours can be connected using these bridges, and several bridges may join the same pair.
A cheapest network is a set of bridges that connects all harbours with minimum total cost (a minimum spanning tree). A bridge is critical if it belongs to every cheapest network, and flexible if it belongs to at least one but not all of them. Bridges that appear in no cheapest network are in neither group.
Return a list of two lists: first the identifiers of all critical bridges, then the identifiers of all flexible bridges. Each inner list is sorted in ascending order and may be empty.
Example 1
- Input:
- n = 5edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[3,4,3],[1,3,4]]
- Output:
- [[0,1,4],[2,3]]
- Explanation:
Edges 0, 1 (weight 1) and 4 (the only link to harbour 4) are in every cheapest network. Edges 2 and 3 both connect the group {0, 1, 2} to harbour 3 at weight 2 and either one alone will do, so they are flexible; edge 5 is never useful. The answer is [[0, 1, 4], [2, 3]].
Example 2
- Input:
- n = 3, edges = [[0,1,5],[1,2,5],[0,2,5]]
- Output:
- [[],[0,1,2]]
- Explanation:
Any two of the three equal-weight edges form a cheapest tree, so no edge is in all of them and every edge is in some of them.
Example 3
- Input:
- n = 4, edges = [[0,1,1],[1,2,1],[2,3,1]]
- Output:
- [[0,1,2],[]]
- Explanation:
The graph is already a tree, so every edge is critical and none is merely pseudo-critical.
Constraints
- 1 ≤ n ≤ 105
- n - 1 ≤ edges.length ≤ 2 * 105 (and the graph is connected)
- 0 ≤ a, b < n, a ≠ b
- 1 ≤ w ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(m log m)
- Space
- O(n + m)