Making wired Connections
Problem Statement
There are n computers numbered from 0 to n-1 connected by ethernet cables (edges). You can remove a cable between two directly connected computers and place it between any pair of disconnected computers. Return the minimum number of cable moves needed to connect all computers, or -1 if it's impossible.
Example:
- Input:
n = 4, connections = [[0,1],[0,2],[1,2]] - Output:
1(remove one cable from the triangle and use it to connect computer 3)
Noob-Friendly Explanation
Imagine you have a bunch of computers in an office, and some are connected with cables. Some groups of computers are connected to each other but NOT to other groups. You need ALL computers to be one big connected network.
The good news: if there's a triangle (A→B→C→A), one of those cables is "extra" — you can remove it and use it to connect two separate groups. You need exactly (number of separate groups - 1) extra cables to connect everything. But first, you need at least n-1 cables total (minimum to connect n computers).
Approach 1: Brute Force (BFS/DFS to Count Components)
Intuition
Use BFS/DFS to count the number of connected components. The answer is (components - 1) because each extra cable can merge two components. First check if we have enough cables: we need at least n-1.
Algorithm
- If number of cables < n-1, return -1 (impossible).
- Build an adjacency list.
- Use BFS/DFS to count connected components.
- Return (components - 1).
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class WiredConnectionsBFS {
public static int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) return -1; // not enough cables
// Build adjacency list
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] conn : connections) {
adj.get(conn[0]).add(conn[1]);
adj.get(conn[1]).add(conn[0]);
}
// Count connected components using BFS
boolean[] visited = new boolean[n];
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
components++;
Queue<Integer> queue = new LinkedList<>();
visited[i] = true;
queue.add(i);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
}
return components - 1;
}
public static void main(String[] args) {
int n = 4;
int[][] connections = {{0,1},{0,2},{1,2}};
System.out.println(makeConnected(n, connections)); // 1
}
}Complexity Analysis
- Time Complexity: O(V + E) — BFS visits each vertex and edge once.
- Space Complexity: O(V + E) — for the adjacency list, visited array, and queue.
Approach 2: Optimal (Union-Find / Disjoint Set Union)
Intuition
Use Union-Find (DSU) data structure. Initially, each computer is its own component. For each cable, merge the two components. After processing all cables, the number of remaining separate components minus 1 is the answer.
Algorithm
- If cables < n-1, return -1.
- Initialize Union-Find with n components.
- For each cable, union the two computers.
- Count the number of distinct components.
- Return (components - 1).
public class WiredConnectionsUF {
static int[] parent;
static int[] rank;
static int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
static boolean union(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false; // already connected
if (rank[px] < rank[py]) {
parent[px] = py;
} else if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[py] = px;
rank[px]++;
}
return true;
}
public static int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) return -1;
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int components = n;
for (int[] conn : connections) {
if (union(conn[0], conn[1])) {
components--;
}
}
return components - 1;
}
public static void main(String[] args) {
int n = 4;
int[][] connections = {{0,1},{0,2},{1,2}};
System.out.println(makeConnected(n, connections)); // 1
}
}Complexity Analysis
- Time Complexity: O(V + E × α(V)) ≈ O(V + E) — Union-Find with path compression and union by rank is nearly O(1) per operation.
- Space Complexity: O(V) — for the parent and rank arrays.