Asked at

Number Of Operations To Make Network Connected

Medium
VerifiedUnion FindGraphDFS~25 min

You have n computers labeled 0..n-1 linked by connections, each [a, b] a cable between two computers. You may unplug any cable and reconnect it elsewhere.

Return the minimum number of cable moves needed to connect every computer into one network, or -1 if there are too few cables.

The input arrives as a single object { n, connections }.

Examples

in{ n: 4, connections: [[0,1],[0,2],[1,2]] }
out1

Move the redundant cable in the triangle to attach computer 3.

in{ n: 6, connections: [[0,1],[0,2],[0,3],[1,2]] }
out-1

Only 4 cables for 6 computers; at least 5 are needed.

Constraints

  • 1 ≤ n ≤ 10⁵
  • connections[i] = [a, b], computers labeled 0..n-1
  • No repeated connections; no self-connections.
  • Each cable joins two computers and can be moved.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.