616. Number of Operations to Make Network Connected
A data center has n computers, labeled 0 through n − 1, wired together by a list connections where each entry [a, b] is a cable directly linking computers a and b. Any computer can talk to any other as long as some chain of cables joins them.
In one operation you may unplug an existing cable and replug it between any two computers of your choice.
Given n and connections, return the minimum number of operations needed so that every computer can reach every other. If it cannot be done with the cables available, return -1.
Example 1:
Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Computers 0, 1, 2 form a triangle and computer 3 is stranded. The cable between 1 and 2 is redundant — moving it to connect 3 (say, 1–3) joins everything: one operation.
Example 2:
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2
Explanation: Computers 0–3 form one cluster with two spare cables; computers 4 and 5 are isolated. Two moves rewire the two spares to reach 4 and 5.
Constraints:
- 1 ≤ n ≤ 10⁵
- 0 ≤ connections.length ≤ min(n·(n-1)/2, 10⁵)
- connections[i].length == 2
- 0 ≤ a, b < n and a ≠ b
- No cable is listed twice, and no computer is cabled to itself.
Hints:
Connecting n computers requires at least n − 1 cables, no matter how cleverly you rewire. If you have fewer, answer -1 immediately.
Group the computers into connected components. Each operation can take one spare cable and stitch two components together — so how many stitches do you need?
If there are c components and at least n − 1 cables in total, the answer is exactly c − 1. Count c with a DFS or, more directly, union-find.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Expected output: 1