PPractick

The problem

An office has n computers joined by some network cables. An IT technician can unplug any cable and reconnect it between two other computers. What's the minimum number of such moves to connect every computer, or −1 if it's impossible? Connecting n computers needs at least n − 1 cables, so with fewer it's impossible. Otherwise, redundant cables (those inside an already-connected group) can be moved, and each move links one more group. The answer is (number of components) − 1, which union-find counts.

Example: n = 4, cables 0-1, 0-2, 1-2 → 1 (move the redundant 1-2 cable to computer 3).

Function signature

int makeConnected(int n, const vector<pair<int, int>>& connections);

Test cases

Input (n, connections)	Output	Explanation
(4, [[0,1],[0,2],[1,2]])	1	Two components; one spare cable
(6, [[0,1],[0,2],[0,3],[1,2],[1,3]])	2	Components {0,1,2,3}, {4}, {5}
(6, [[0,1],[0,2],[0,3],[1,2]])	-1	Only 4 cables for 6 computers
(3, [[0,1],[1,2]])	0	Already connected
(1, [])	0

(Confirm: cables are undirected with no duplicates; a move relocates one existing cable.)

How interviewers phrase it

• "Return the minimum number of times you need to move cables to make all the computers connected; if it's not possible, return −1" (LeetCode 1319).

Clarifying questions to ask

1. Can we only move existing cables, not add new ones? (Yes.)
2. Are there duplicate cables? (No.)
3. How large? (n up to 10⁵.)

Follow-ups to expect

1. "Why components − 1?"
2. "Where do the spare cables come from?"
3. "Why check the total first?"
4. "BFS or DFS instead of DSU?"
5. "Complexity?"

Related questions

• Prim's Algorithm Hard
• Disjoint Set Hard
• Find the MST weight Hard
• Accounts merge Hard
• Number of islands II Hard
• Making a large island Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in