Making wired connections / redundant connection (components)
Problem
(1) Making Wired Connections: n computers and a list of cables. You may unplug any cable and reconnect it elsewhere. Return the minimum number of moves needed to connect every computer, or −1 if there are too few cables (fewer than n − 1). (2) Redundant Connection: a tree had one extra edge added — return the edge that creates the cycle (the last such edge in the input).
Example 1
Input: n = 4, connections = [[0,1], [0,2], [1,2]] Output: 1
Example 2
Input: redundant: [[1,2], [1,3], [2,3]] Output: [2, 3]
Also asked as: Making wired Connections
Test cases
Case 1
Input: 4, [[0,1],[0,2],[1,2]] Expected: 1
Case 2
Input: 6, [[0,1],[0,2],[0,3],[1,2],[1,3]] Expected: 2
Case 3
Input: 6, [[0,1],[0,2],[0,3],[1,2]] Expected: -1
View solutionHide solution1 approach
1. Union-Find — extra cables vs components to join
Time O(E α(V))Space O(V)
Each edge that connects two already-connected nodes is a spare cable. You can connect c components if you have ≥ c−1 spare cables.
function makeConnected(n, connections) { if (connections.length < n - 1) return -1; const parent = Array.from({ length: n }, (_, i) => i); const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x]))); let components = n; for (const [a, b] of connections) { const ra = find(a), rb = find(b); if (ra !== rb) { parent[ra] = rb; components--; } } return components - 1; // moves needed to link all components}