#240HardGraphs· Minimum Spanning Tree Edge Classification

Critical Backbone Links

A network team plans a backbone connecting `n` sites. Link `i` is described by `links[i] = [u, v, w]`: it joins sites `u` and `v` in both directions at cost `w`. The sites are connected overall. The team will build a **minimum spanning tree**: a set of links that connects every site with the smallest possible total cost. Several different cheapest trees may exist. Classify the links by index: - **critical**: the link is part of **every** minimum spanning tree (removing it would make the backbone more expensive or disconnect it); - **flexible**: the link is part of **some** but **not all** minimum spanning trees. Links that appear in no minimum spanning tree are in neither list. Return `[critical, flexible]`, each list sorted ascending by link index.

Input format

`n`: the number of sites. `links`: an array of `[u, v, w]`.

Output format

An array of two arrays of link indices: [critical, flexible].

Examples

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

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

Links 0 and 1 (cost 1) and the cost-3 pair are forced by the cuts they cross: links 0 and 1 are critical. Links 2 and 3 tie for connecting site 3, and 4 and 5 tie for connecting site 4, so 2, 3, 4 and 5 are flexible. Link 6 is too expensive.

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

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

A square of equal costs: any three of the four links form a cheapest tree, so no link is critical and all four are flexible.

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

Output: [[0], []]

The single link is the only way to connect the two sites, so it is critical.

Constraints

2 <= n <= 100
n - 1 <= links.length <= 200
0 <= u, v < n, u != v
1 <= w <= 1000
The graph is connected; parallel links are allowed.

#graphs
#minimum-spanning-tree
#kruskal
#union-find