FastPrep
Problem

Minimum Spanning Tree Weight in a Complete Binary Graph

UberFULLTIMEOA
See Uber hiring insights

You are given n nodes in a complete undirected graph. Some edges have weight 1; every other edge has weight 0. The weight-1 edges are given in the array oneEdges, where each edge is represented as [u, v].

Return the total weight of a minimum spanning tree of this complete graph.

Examples
01 · Example 1
n = 4
oneEdges = [[1, 2], [2, 3], [3, 4]]
return = 0

All edges not listed in oneEdges have weight 0. The zero-weight edges can connect all four nodes, so the MST weight is 0.

02 · Example 2
n = 3
oneEdges = [[1, 2], [1, 3], [2, 3]]
return = 2

Every edge has weight 1, so any spanning tree uses two weight-1 edges.

Constraints
  • 1 <= n <= 2 * 10^5
  • 0 <= oneEdges.length <= min(n * (n - 1) / 2, 2 * 10^5)
  • 1 <= u < v <= n for each edge in oneEdges
  • oneEdges contains no duplicate edges.
More Uber problems
drafts saved locally
public int minimumSpanningTreeWeight(int n, int[][] oneEdges) {
  // write your code here
}
n4
oneEdges[[1, 2], [2, 3], [3, 4]]
expected0
sign in to submit