Medium · Graphs

Union-Find · Kruskal MST

Given n nodes and undirected weighted edges [u, v, w], return the edges of a minimum spanning tree (a minimum spanning forest if the graph is disconnected) in the order Kruskal accepts them — by weight, equal weights in input order — together with their total weight.

Examples

Example 1

{
  "n": 5,
  "edges": [
    [0, 1, 2],
    [0, 3, 6],
    [1, 2, 3],
    [1, 3, 8],
    [1, 4, 5],
    [2, 4, 7],
    [3, 4, 9]
  ],
  "pos": [
    [160, 40],
    [60, 120],
    [110, 220],
    [260, 120],
    [210, 220]
  ]
}

Output: MST 16: [0,1,2] [1,2,3] [1,4,5] [0,3,6]

Example 2

{
  "n": 6,
  "edges": [
    [0, 1, 4],
    [0, 2, 3],
    [1, 2, 1],
    [1, 3, 2],
    [2, 3, 4],
    [3, 4, 2],
    [4, 5, 6],
    [2, 5, 5]
  ],
  "pos": [
    [60, 60],
    [180, 40],
    [120, 140],
    [240, 140],
    [180, 230],
    [60, 200]
  ]
}

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

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.