Number of Operations to Make Network Connected

🎯

Number of Operations to Make Network Connected

mediumGRAPHAmazonGoogleFacebook

Imagine you are a network engineer trying to connect all computers in a network with the minimum number of cable operations.

💡 This problem involves understanding how to efficiently connect components in a network. Beginners often struggle because they try to simulate connections naively or don't realize the importance of counting connected components and spare edges.

📋

Problem Statement

You are given n computers numbered from 0 to n-1 and a list of connections where each connection connects two computers. You need to determine the minimum number of operations to connect all computers so that every computer can reach every other computer. An operation consists of removing an existing cable and placing it between two disconnected computers. Return the minimum number of operations needed, or -1 if it is impossible to connect all computers.

1 ≤ n ≤ 10^51 ≤ connections.length ≤ 10^5connections[i].length == 20 ≤ connections[i][0], connections[i][1] < nNo duplicate connectionsNo self-connections (connections[i][0] != connections[i][1])

💡

Example

Input"n = 4, connections = [[0,1],[0,2],[1,2]]"

Output1

There are 3 computers connected with 3 cables. One cable can be moved to connect the 4th computer.

Input"n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]"

Output2

There are 5 cables connecting 4 computers. Two operations are needed to connect all 6 computers.

Input"n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]"

Output-1

There are only 4 cables, which is less than n-1=5, so it's impossible to connect all computers.

• n = 1, connections = [] → 0 (single computer is trivially connected)
• n = 2, connections = [] → -1 (no cables to connect two computers)
• n = 3, connections = [[0,1],[1,2],[0,2]] → 0 (already fully connected with extra cable)
• n = 5, connections = [[0,1],[2,3]] → -1 (not enough cables to connect all)

⚠️

Common Mistakes

Not checking if number of cables is at least n-1 before processing

Returns wrong answer or wastes time processing impossible cases

✅ Add early check: if connections.length < n - 1, return -1 immediately

Using DFS without marking visited nodes correctly

Infinite loops or incorrect component counts

✅ Use a visited set or array and mark nodes as visited before recursion or iteration

Union-find without path compression or rank optimization

Slower performance, possibly TLE on large inputs

✅ Implement path compression in find and use rank to keep trees shallow

Returning components count instead of components - 1

Off-by-one error in final answer

✅ Return number of connected components minus one as minimum operations

Not handling the case n=1 correctly

May return -1 or incorrect result

✅ Recognize single node is trivially connected, return 0

🧠

Brute Force (Graph Traversal + Counting Components)

💡 This approach exists to build intuition by explicitly counting connected components using DFS or BFS and checking if enough cables exist. It is straightforward but inefficient for large inputs.

Intuition

Count how many connected components exist by traversing the graph. If the number of cables is less than n-1, return -1. Otherwise, the minimum operations needed is the number of components minus one.

Algorithm

1. Build adjacency list from connections.
2. Initialize visited set and count connected components using DFS.
3. Check if number of cables < n - 1; if yes, return -1.
4. Return number of connected components - 1 as minimum operations.

💡 The challenge is to realize that connecting all components requires at least n-1 cables and that the number of operations equals the number of disconnected groups minus one.

</>

Code

from collections import defaultdict

def makeConnected(n, connections):
    if len(connections) < n - 1:
        return -1
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    visited = set()
    def dfs(node):
        visited.add(node)  # Mark starting node visited
        stack = [node]
        while stack:
            curr = stack.pop()
            for nei in graph[curr]:
                if nei not in visited:
                    visited.add(nei)
                    stack.append(nei)
    components = 0
    for i in range(n):
        if i not in visited:
            dfs(i)
            components += 1
    return components - 1

# Driver code
if __name__ == '__main__':
    print(makeConnected(4, [[0,1],[0,2],[1,2]]))  # Output: 1
    print(makeConnected(6, [[0,1],[0,2],[0,3],[1,2],[1,3]]))  # Output: 2
    print(makeConnected(6, [[0,1],[0,2],[0,3],[1,2]]))  # Output: -1

Line Notes

if len(connections) < n - 1:Check if there are enough cables to connect all computers; if not, return -1 immediately

graph = defaultdict(list)Build adjacency list to represent the network graph

for u, v in connections:Populate adjacency list for undirected graph

visited = set()Track visited nodes to avoid revisiting during DFS

def dfs(node):Define DFS to explore all nodes in a connected component

visited.add(node) # Mark starting node visitedMark the starting node as visited before DFS to ensure it's counted

stack = [node]Use stack for iterative DFS to avoid recursion limits

for i in range(n):Iterate over all computers to find disconnected components

if i not in visited:Start DFS from unvisited nodes to count components

components += 1Increment count for each connected component found

return components - 1Minimum operations equals number of components minus one

import java.util.*;

public class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] conn : connections) {
            graph.get(conn[0]).add(conn[1]);
            graph.get(conn[1]).add(conn[0]);
        }
        boolean[] visited = new boolean[n];
        int components = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, graph, visited);
                components++;
            }
        }
        return components - 1;
    }

    private void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
        Stack<Integer> stack = new Stack<>();
        stack.push(node);
        visited[node] = true;
        while (!stack.isEmpty()) {
            int curr = stack.pop();
            for (int nei : graph.get(curr)) {
                if (!visited[nei]) {
                    visited[nei] = true;
                    stack.push(nei);
                }
            }
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.makeConnected(4, new int[][]{{0,1},{0,2},{1,2}})); // 1
        System.out.println(sol.makeConnected(6, new int[][]{{0,1},{0,2},{0,3},{1,2},{1,3}})); // 2
        System.out.println(sol.makeConnected(6, new int[][]{{0,1},{0,2},{0,3},{1,2}})); // -1
    }
}

Line Notes

if (connections.length < n - 1) return -1;Quick check for insufficient cables to connect all computers

List<List<Integer>> graph = new ArrayList<>();Initialize adjacency list for graph representation

for (int[] conn : connections)Build undirected graph edges

boolean[] visited = new boolean[n];Track visited nodes during DFS

for (int i = 0; i < n; i++)Iterate over all nodes to find disconnected components

if (!visited[i])Start DFS from unvisited node to explore a component

Stack<Integer> stack = new Stack<>();Use stack for iterative DFS to avoid recursion overhead

visited[node] = true;Mark node as visited to prevent revisiting

return components - 1;Operations needed equals number of components minus one

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) return -1;
        vector<vector<int>> graph(n);
        for (auto& conn : connections) {
            graph[conn[0]].push_back(conn[1]);
            graph[conn[1]].push_back(conn[0]);
        }
        vector<bool> visited(n, false);
        int components = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, graph, visited);
                components++;
            }
        }
        return components - 1;
    }

private:
    void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
        stack<int> stk;
        stk.push(node);
        visited[node] = true;
        while (!stk.empty()) {
            int curr = stk.top();
            stk.pop();
            for (int nei : graph[curr]) {
                if (!visited[nei]) {
                    visited[nei] = true;
                    stk.push(nei);
                }
            }
        }
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> con1 = {{0,1},{0,2},{1,2}};
    cout << sol.makeConnected(4, con1) << "\n"; // 1
    vector<vector<int>> con2 = {{0,1},{0,2},{0,3},{1,2},{1,3}};
    cout << sol.makeConnected(6, con2) << "\n"; // 2
    vector<vector<int>> con3 = {{0,1},{0,2},{0,3},{1,2}};
    cout << sol.makeConnected(6, con3) << "\n"; // -1
    return 0;
}

Line Notes

if (connections.size() < n - 1) return -1;Check if enough cables exist to connect all computers

vector<vector<int>> graph(n);Create adjacency list for graph

for (auto& conn : connections)Build undirected graph edges

vector<bool> visited(n, false);Track visited nodes during DFS

for (int i = 0; i < n; i++)Iterate over all nodes to find connected components

if (!visited[i])Start DFS from unvisited node to explore component

stack<int> stk;Use stack for iterative DFS to avoid recursion

visited[node] = true;Mark node visited to prevent revisiting

return components - 1;Minimum operations equals components minus one

function makeConnected(n, connections) {
    if (connections.length < n - 1) return -1;
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of connections) {
        graph[u].push(v);
        graph[v].push(u);
    }
    const visited = new Set();
    function dfs(node) {
        visited.add(node); // Mark starting node visited
        const stack = [node];
        while (stack.length > 0) {
            const curr = stack.pop();
            for (const nei of graph[curr]) {
                if (!visited.has(nei)) {
                    visited.add(nei);
                    stack.push(nei);
                }
            }
        }
    }
    let components = 0;
    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            dfs(i);
            components++;
        }
    }
    return components - 1;
}

// Driver code
console.log(makeConnected(4, [[0,1],[0,2],[1,2]])); // 1
console.log(makeConnected(6, [[0,1],[0,2],[0,3],[1,2],[1,3]])); // 2
console.log(makeConnected(6, [[0,1],[0,2],[0,3],[1,2]])); // -1

Line Notes

if (connections.length < n - 1) return -1;Check if there are enough cables to connect all computers

const graph = Array.from({length: n}, () => []);Initialize adjacency list for graph

for (const [u, v] of connections)Build undirected graph edges

const visited = new Set();Track visited nodes during DFS

function dfs(node)Define DFS to explore connected components

visited.add(node); // Mark starting node visitedMark the starting node as visited before DFS to ensure it's counted

const stack = [node];Use stack for iterative DFS to avoid recursion

for (let i = 0; i < n; i++)Iterate over all nodes to find disconnected components

if (!visited.has(i))Start DFS from unvisited node to count components

return components - 1;Operations needed equals number of components minus one

⏱

Complexity

TimeO(n + connections.length)

SpaceO(n + connections.length)

Building the graph takes O(connections.length). DFS visits each node and edge once, totaling O(n + connections.length).

💡 For n=100,000 and connections=100,000, this approach is efficient enough to run within seconds.

Interview Verdict: Accepted

This approach is efficient enough for the problem constraints and is a good baseline solution.

🧠

Union-Find (Disjoint Set Union) Approach

💡 Union-Find is a classic data structure to efficiently track connected components. This approach is faster and cleaner than DFS for large inputs and is a must-know technique for network connectivity problems.

Intuition

Use union-find to merge connected computers. Count how many connected components remain. If cables are insufficient, return -1. Otherwise, operations needed equals components minus one.

Algorithm

1. Initialize union-find data structure with n separate sets.
2. For each connection, union the two computers.
3. Count how many unique parents (connected components) remain.
4. If cables < n - 1, return -1; else return components - 1.

💡 Union-find abstracts away graph traversal and provides near O(1) union and find operations, making it ideal for large datasets.

</>

Code

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            self.count -= 1


def makeConnected(n, connections):
    if len(connections) < n - 1:
        return -1
    uf = UnionFind(n)
    for u, v in connections:
        uf.union(u, v)
    return uf.count - 1

# Driver code
if __name__ == '__main__':
    print(makeConnected(4, [[0,1],[0,2],[1,2]]))  # 1
    print(makeConnected(6, [[0,1],[0,2],[0,3],[1,2],[1,3]]))  # 2
    print(makeConnected(6, [[0,1],[0,2],[0,3],[1,2]]))  # -1

Line Notes

self.parent = list(range(n))Initialize each node as its own parent (self root)

self.rank = [0] * nRank array to keep tree shallow during unions

if self.parent[x] != x:Path compression to flatten tree for fast finds

if rootX != rootY:Only union if roots differ to avoid cycles

self.count -= 1Decrement count of connected components after union

if len(connections) < n - 1:Check if enough cables exist before union operations

uf = UnionFind(n)Create union-find instance for n computers

for u, v in connections:Union connected computers

return uf.count - 1Operations needed equals number of components minus one

class UnionFind {
    int[] parent, rank;
    int count;
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
        }
    }
}

public class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;
        UnionFind uf = new UnionFind(n);
        for (int[] conn : connections) uf.union(conn[0], conn[1]);
        return uf.count - 1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.makeConnected(4, new int[][]{{0,1},{0,2},{1,2}})); // 1
        System.out.println(sol.makeConnected(6, new int[][]{{0,1},{0,2},{0,3},{1,2},{1,3}})); // 2
        System.out.println(sol.makeConnected(6, new int[][]{{0,1},{0,2},{0,3},{1,2}})); // -1
    }
}

Line Notes

parent = new int[n];Initialize parent array where each node is its own parent

rank = new int[n];Rank array to optimize union operations

if (parent[x] != x) parent[x] = find(parent[x]);Path compression to speed up find

if (rootX != rootY)Union only if roots differ to avoid cycles

count--;Decrease count of connected components after union

if (connections.length < n - 1) return -1;Check if enough cables exist before unions

UnionFind uf = new UnionFind(n);Create union-find instance

for (int[] conn : connections) uf.union(conn[0], conn[1]);Union connected computers

return uf.count - 1;Operations needed equals components minus one

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> parent, rank;
    int count;
    UnionFind(int n) : parent(n), rank(n, 0), count(n) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
        }
    }
};

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) return -1;
        UnionFind uf(n);
        for (auto& conn : connections) uf.unite(conn[0], conn[1]);
        return uf.count - 1;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> con1 = {{0,1},{0,2},{1,2}};
    cout << sol.makeConnected(4, con1) << "\n"; // 1
    vector<vector<int>> con2 = {{0,1},{0,2},{0,3},{1,2},{1,3}};
    cout << sol.makeConnected(6, con2) << "\n"; // 2
    vector<vector<int>> con3 = {{0,1},{0,2},{0,3},{1,2}};
    cout << sol.makeConnected(6, con3) << "\n"; // -1
    return 0;
}

Line Notes

vector<int> parent, rank;Parent and rank arrays for union-find structure

for (int i = 0; i < n; i++) parent[i] = i;Initialize each node as its own parent

if (parent[x] != x) parent[x] = find(parent[x]);Path compression to speed up find

if (rootX != rootY)Union only if roots differ to avoid cycles

count--;Decrement connected components count after union

if (connections.size() < n - 1) return -1;Check if enough cables exist before union operations

UnionFind uf(n);Create union-find instance

for (auto& conn : connections) uf.unite(conn[0], conn[1]);Union connected computers

return uf.count - 1;Operations needed equals components minus one

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
        this.count = n;
    }
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }
    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        if (rootX !== rootY) {
            if (this.rank[rootX] < this.rank[rootY]) {
                this.parent[rootX] = rootY;
            } else if (this.rank[rootX] > this.rank[rootY]) {
                this.parent[rootY] = rootX;
            } else {
                this.parent[rootY] = rootX;
                this.rank[rootX]++;
            }
            this.count--;
        }
    }
}

function makeConnected(n, connections) {
    if (connections.length < n - 1) return -1;
    const uf = new UnionFind(n);
    for (const [u, v] of connections) {
        uf.union(u, v);
    }
    return uf.count - 1;
}

// Driver code
console.log(makeConnected(4, [[0,1],[0,2],[1,2]])); // 1
console.log(makeConnected(6, [[0,1],[0,2],[0,3],[1,2],[1,3]])); // 2
console.log(makeConnected(6, [[0,1],[0,2],[0,3],[1,2]])); // -1

Line Notes

this.parent = Array.from({length: n}, (_, i) => i);Initialize each node as its own parent

this.rank = new Array(n).fill(0);Rank array to keep trees shallow

if (this.parent[x] !== x)Path compression to speed up find

if (rootX !== rootY)Union only if roots differ to avoid cycles

this.count--;Decrement count of connected components after union

if (connections.length < n - 1) return -1;Check if enough cables exist before unions

const uf = new UnionFind(n);Create union-find instance

for (const [u, v] of connections)Union connected computers

return uf.count - 1;Operations needed equals components minus one

⏱

Complexity

TimeO(α(n) * connections.length)

SpaceO(n)

Union-find operations are almost O(1) amortized (α is inverse Ackermann function). We perform union for each connection.

💡 For n=100,000, this approach is very efficient and scales well.

Interview Verdict: Accepted

Union-find is the optimal approach for this problem and is preferred in interviews.

🧠

Optimized Union-Find with Early Stopping

💡 This approach improves the union-find by stopping early once all computers are connected, saving unnecessary unions and improving runtime in practice.

Intuition

Track the number of connected components during union operations. Once only one component remains, stop processing further connections.

Algorithm

1. Initialize union-find with n sets and count = n.
2. Iterate over connections, union sets and decrement count.
3. If count reaches 1, return 0 immediately (already connected).
4. If after processing all connections count > 1, check cables count and return count - 1 or -1.

💡 Early stopping avoids unnecessary unions and can speed up large inputs with many redundant cables.

</>

Code

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            self.count -= 1
            return True
        return False


def makeConnected(n, connections):
    if len(connections) < n - 1:
        return -1
    uf = UnionFind(n)
    for u, v in connections:
        uf.union(u, v)
        if uf.count == 1:
            return 0
    return uf.count - 1

# Driver code
if __name__ == '__main__':
    print(makeConnected(4, [[0,1],[0,2],[1,2]]))  # 1
    print(makeConnected(6, [[0,1],[0,2],[0,3],[1,2],[1,3]]))  # 2
    print(makeConnected(6, [[0,1],[0,2],[0,3],[1,2]]))  # -1

Line Notes

self.count = nTrack number of connected components

if rootX != rootY:Union only if roots differ to avoid cycles

self.count -= 1Decrement count after successful union

return TrueIndicate union was successful

if len(connections) < n - 1:Check if enough cables exist before unions

for u, v in connections:Union connected computers

if uf.count == 1:Early stop if all computers connected

return uf.count - 1Return minimum operations needed

class UnionFind {
    int[] parent, rank;
    int count;
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
            return true;
        }
        return false;
    }
}

public class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;
        UnionFind uf = new UnionFind(n);
        for (int[] conn : connections) {
            uf.union(conn[0], conn[1]);
            if (uf.count == 1) return 0;
        }
        return uf.count - 1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.makeConnected(4, new int[][]{{0,1},{0,2},{1,2}})); // 1
        System.out.println(sol.makeConnected(6, new int[][]{{0,1},{0,2},{0,3},{1,2},{1,3}})); // 2
        System.out.println(sol.makeConnected(6, new int[][]{{0,1},{0,2},{0,3},{1,2}})); // -1
    }
}

Line Notes

int count;Track number of connected components

if (rootX != rootY)Union only if roots differ to avoid cycles

count--;Decrement count after successful union

return true;Indicate union was successful

if (connections.length < n - 1) return -1;Check if enough cables exist before unions

for (int[] conn : connections)Union connected computers

if (uf.count == 1) return 0;Early stop if all computers connected

return uf.count - 1;Return minimum operations needed

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> parent, rank;
    int count;
    UnionFind(int n) : parent(n), rank(n, 0), count(n) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
            return true;
        }
        return false;
    }
};

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) return -1;
        UnionFind uf(n);
        for (auto& conn : connections) {
            uf.unite(conn[0], conn[1]);
            if (uf.count == 1) return 0;
        }
        return uf.count - 1;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> con1 = {{0,1},{0,2},{1,2}};
    cout << sol.makeConnected(4, con1) << "\n"; // 1
    vector<vector<int>> con2 = {{0,1},{0,2},{0,3},{1,2},{1,3}};
    cout << sol.makeConnected(6, con2) << "\n"; // 2
    vector<vector<int>> con3 = {{0,1},{0,2},{0,3},{1,2}};
    cout << sol.makeConnected(6, con3) << "\n"; // -1
    return 0;
}

Line Notes

int count;Track number of connected components

if (rootX != rootY)Union only if roots differ to avoid cycles

count--;Decrement count after successful union

return true;Indicate union was successful

if (connections.size() < n - 1) return -1;Check if enough cables exist before unions

for (auto& conn : connections)Union connected computers

if (uf.count == 1) return 0;Early stop if all computers connected

return uf.count - 1;Return minimum operations needed

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
        this.count = n;
    }
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }
    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        if (rootX !== rootY) {
            if (this.rank[rootX] < this.rank[rootY]) {
                this.parent[rootX] = rootY;
            } else if (this.rank[rootX] > this.rank[rootY]) {
                this.parent[rootY] = rootX;
            } else {
                this.parent[rootY] = rootX;
                this.rank[rootX]++;
            }
            this.count--;
            return true;
        }
        return false;
    }
}

function makeConnected(n, connections) {
    if (connections.length < n - 1) return -1;
    const uf = new UnionFind(n);
    for (const [u, v] of connections) {
        uf.union(u, v);
        if (uf.count === 1) return 0;
    }
    return uf.count - 1;
}

// Driver code
console.log(makeConnected(4, [[0,1],[0,2],[1,2]])); // 1
console.log(makeConnected(6, [[0,1],[0,2],[0,3],[1,2],[1,3]])); // 2
console.log(makeConnected(6, [[0,1],[0,2],[0,3],[1,2]])); // -1

Line Notes

this.count = n;Track number of connected components

if (rootX !== rootY)Union only if roots differ to avoid cycles

this.count--;Decrement count after successful union

return true;Indicate union was successful

if (connections.length < n - 1) return -1;Check if enough cables exist before unions

for (const [u, v] of connections)Union connected computers

if (uf.count === 1) return 0;Early stop if all computers connected

return uf.count - 1;Return minimum operations needed

⏱

Complexity

TimeO(α(n) * connections.length)

SpaceO(n)

Early stopping can reduce runtime in practice but worst case remains same as union-find.

💡 Early stopping is a practical optimization that can save time on large inputs with many redundant cables.

Interview Verdict: Accepted

This is an optimized version of union-find that is preferred in interviews for efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Union-find is the preferred approach in 95% of interviews due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS to count components)	O(n + connections.length)	O(n + connections.length)	Possible with deep recursion	Yes	Good to mention for intuition, but not preferred to code
2. Union-Find (Disjoint Set Union)	O(α(n) * connections.length)	O(n)	No	Yes	Optimal approach to implement in interviews
3. Optimized Union-Find with Early Stopping	O(α(n) * connections.length) with early exit	O(n)	No	Yes	Best practical approach, mention optimization if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, and progress to union-find approaches. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe brute force approach using DFS to count components.Step 3: Explain why union-find is more efficient and implement it.Step 4: Discuss optimizations like early stopping.Step 5: Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of graph connectivity, ability to implement union-find, and optimization skills.

Common Follow-ups

• What if the network is dynamic with connections added or removed? → Use dynamic connectivity data structures.
• Can you optimize space usage? → Use union-find with path compression and rank.

💡 Follow-ups test your ability to adapt the solution to dynamic scenarios and optimize data structures.

🔍

Pattern Recognition

When to Use

Use union-find when asked to connect components, count connected groups, or detect cycles in undirected graphs.

Signature Phrases

'minimum number of operations to connect all computers''connections between nodes''network is connected if every node can reach every other node'

NOT This Pattern When

Problems involving shortest paths, weighted edges, or directed graphs usually require different techniques like Dijkstra or topological sort.

Similar Problems

Number of Connected Components in an Undirected Graph - counting components with DFS or union-findRedundant Connection - detecting extra edges using union-findGraph Valid Tree - checking if graph is connected and acyclic

Practice

1. Consider the following code snippet that finds the number of provinces (connected components) in a city network represented by isConnected. Given the input matrix [[1,1,0],[1,1,0],[0,0,1]], what is the value of the variable provinces after the outer loop completes?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace DFS starting from city 0

   City 0 connects to city 1, so DFS marks city 0 and city 1 visited.

2. Step 2: Continue outer loop and count provinces

   City 2 is not visited, so DFS marks city 2 visited. Total provinces counted = 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two connected groups: {0,1} and {2} [OK]

Hint: Count DFS starts on unvisited nodes [OK]

Common Mistakes:

• Counting all nodes as provinces
• Off-by-one in counting provinces

2. What is the time complexity of the optimal Union-Find algorithm with path compression and union by rank when finding the redundant connection in a graph with n edges?

medium

A. O(n²) because each union operation may traverse all nodes

B. O(n * α(n)) where α(n) is the inverse Ackermann function, nearly constant

C. O(n log n) due to sorting edges before union operations

D. O(n) because each edge is processed once without overhead

Solution

1. Step 1: Identify number of union/find operations

   There are n edges, each triggers at most one union and two finds.

2. Step 2: Analyze complexity of find with path compression and union by rank

   Each find/union operation runs in amortized O(α(n)) time, where α(n) is inverse Ackermann function, which grows extremely slowly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Union-Find with optimizations runs in near-linear time O(n * α(n)) [OK]

Hint: Inverse Ackermann function α(n) is almost constant [OK]

Common Mistakes:

• Assuming O(n²) due to nested loops
• Confusing sorting complexity with union-find
• Ignoring path compression benefits

3. Consider the following buggy union-find code for satisfiability of equality equations. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line with 'return self.find(self.parent[x])' in find() method

B. Line with 'self.parent[rootX] = rootY' in union() method

C. Line with 'if eq[1:3] == '!=':' in equationsPossible()

D. Line with 'self.rank[rootX] += 1' in union() method

Solution

1. Step 1: Analyze find() method

   The find method recursively calls itself but does not assign the compressed path back to self.parent[x], missing path compression.

2. Step 2: Consequence of missing path compression

   Without path compression, find operations become slower and may cause incorrect root identification in large inputs, potentially missing contradictions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Path compression requires assignment to parent [OK]

Hint: Path compression must assign parent[x] = find(parent[x]) [OK]

Common Mistakes:

• Forgetting path compression assignment
• Incorrect union by rank logic

4. Suppose the problem is modified so that edges can be reused multiple times (i.e., multi-edges allowed), and we want to remove the maximum number of edges while keeping the graph traversable for both Alice and Bob. Which modification to the optimal union-find approach is necessary?

hard

A. Use a multigraph union-find variant that counts edge multiplicities and only removes redundant edges after full connectivity.

B. Switch to a shortest path algorithm since union-find cannot handle multi-edges.

C. No change needed; the original union-find approach works as is.

D. Process edges in arbitrary order without sorting since multi-edges guarantee connectivity.

Solution

1. Step 1: Understand multi-edge impact

   Multi-edges mean multiple edges connect same nodes; union-find alone merges sets once, ignoring multiplicity.

2. Step 2: Modify union-find approach

   Need to track edge counts per connection and only remove edges that do not break connectivity, requiring a multigraph-aware union-find or additional bookkeeping.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Original union-find ignores multiplicity -> must track edge counts [OK]

Hint: Union-find merges sets once; multi-edges require counting edges [OK]

Common Mistakes:

• Assuming union-find handles multi-edges without change
• Ignoring edge multiplicity
• Switching to unrelated algorithms unnecessarily

5. Suppose the problem is extended so that variables can be reused multiple times in equations, and inequalities can be chained (e.g., a==b, b!=c, c==a). Which modification to the union-find approach correctly handles early contradiction detection in this scenario?

hard

A. Process all equalities and inequalities in a single pass, unioning and checking contradictions immediately

B. First union all equalities, then check all inequalities for contradictions, returning false if any found

C. Use union-find with early contradiction detection by checking inequalities during union operations and aborting immediately on conflict

D. Replace union-find with a graph coloring approach to handle chained inequalities

Solution

1. Step 1: Understand reuse and chaining impact

   Variables appearing multiple times and chained inequalities require detecting contradictions as soon as they arise to avoid unnecessary work.

2. Step 2: Early contradiction detection

   Checking inequalities during union operations allows immediate detection of conflicts, improving efficiency and correctness.

3. Step 3: Compare alternatives

   Single pass union and check can miss contradictions; two-pass delays detection; graph coloring is more complex and less efficient here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Early contradiction detection aborts on conflict [OK]

Hint: Check contradictions during union to detect conflicts early [OK]

Common Mistakes:

• Checking inequalities only after all unions
• Trying single pass union and check without order