Making wired connections / redundant connection (components)

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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
}