# Number of Operations to Make Network Connected
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-operations-to-make-network-connected)
Canonical: https://scaleengineer.com/dsa/problems/number-of-operations-to-make-network-connected
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Intuit](https://scaleengineer.com/companies/intuit), [Nvidia](https://scaleengineer.com/companies/nvidia), [Akuna Capital](https://scaleengineer.com/companies/akuna-capital), [McKinsey](https://scaleengineer.com/companies/mckinsey)
---
## Problem
There are `n` computers numbered from `0` to `n - 1` connected by ethernet cables `connections` forming a network where `connections[i] = [ai, bi]` represents a connection between computers `ai` and `bi`. Any computer can reach any other computer directly or indirectly through the network.

You are given an initial computer network `connections`. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected.

Return _the minimum number of times you need to do this in order to make all the computers connected_. If it is not possible, return `-1`.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-operations-to-make-network-connected/image0.png) 

**Input:** n = 4, connections = [[0,1],[0,2],[1,2]]
**Output:** 1
**Explanation:** Remove cable between computer 1 and 2 and place between computers 1 and 3.

**Example 2:**

![](https://assets.glich.co/dsa/number-of-operations-to-make-network-connected/image1.png) 

**Input:** n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
**Output:** 2

**Example 3:**

**Input:** n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
**Output:** -1
**Explanation:** There are not enough cables.

**Constraints:**

* `1 <= n <= 105`
* `1 <= connections.length <= min(n * (n - 1) / 2, 105)`
* `connections[i].length == 2`
* `0 <= ai, bi < n`
* `ai != bi`
* There are no repeated connections.
* No two computers are connected by more than one cable.

# Approaches
## Depth-First Search (DFS) / Breadth-First Search (BFS)
This approach models the network as a graph and uses a standard graph traversal algorithm, like Depth-First Search (DFS), to solve the problem. The core idea is that to connect `k` separate components of a graph, we need `k - 1` connections. The problem thus reduces to finding the number of connected components in the initial network. A prerequisite is having enough cables; a network with `n` computers needs at least `n - 1` cables to be connected. If this condition isn't met, it's impossible to connect the network.
**Time:** O(n + E), where `n` is the number of computers and `E` is the number of connections. Building the adjacency list takes O(E) time. The DFS traversal visits each vertex and edge once, resulting in O(n + E) time. · **Space:** O(n + E). The adjacency list requires O(n + E) space. The `visited` array requires O(n) space, and the recursion stack for DFS can go up to O(n) in the worst case.
**Pros:** Intuitive approach based on standard graph traversal.; Relatively easy to implement if familiar with DFS/BFS.
**Cons:** Requires more space than the Union-Find approach due to the storage of the adjacency list.
### Explanation
First, we perform a quick check: if the number of available cables (`connections.length`) is less than `n - 1`, we cannot connect all `n` computers, so we return -1. Otherwise, a solution is always possible.

We then proceed to count the number of connected components. To do this, we build an adjacency list representation of the graph. We also use a `visited` array to keep track of computers we have already visited. We iterate through each computer from 0 to `n-1`. If a computer hasn't been visited, it means we've found a new, unexplored connected component. We increment our component counter and start a DFS traversal from this computer. The DFS will explore all reachable computers from this starting point, marking them as visited. After iterating through all computers, the counter will hold the total number of connected components.

The minimum number of operations (cable moves) required is this count minus one.

Here is a Java implementation of this approach:
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) {
            return -1;
        }

        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] conn : connections) {
            adj[conn[0]].add(conn[1]);
            adj[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, adj, visited);
                components++;
            }
        }

        return components - 1;
    }

    private void dfs(int u, List<Integer>[] adj, boolean[] visited) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                dfs(v, adj, visited);
            }
        }
    }
}
```
### Algorithm
- Check if `connections.length < n - 1`. If true, return -1.
- Build an adjacency list `adj` from the `connections` array to represent the computer network.
- Initialize a boolean array `visited` of size `n` to all `false`.
- Initialize a counter `components` to 0.
- Loop through each computer `i` from 0 to `n-1`:
  - If `visited[i]` is `false`:
    - Increment `components`.
    - Call a DFS function starting from `i` to traverse the component and mark all its nodes as visited.
- Return `components - 1`.

## Union-Find (Disjoint Set Union)
This approach uses the Union-Find (or Disjoint Set Union) data structure, which is highly optimized for problems involving partitioning a set of elements into a number of disjoint subsets. We can think of each connected component as a disjoint set. The goal is to find the number of such sets. Initially, each of the `n` computers is in its own set. We then process each connection, uniting the sets of the two connected computers. The number of sets that remain after processing all connections gives us the number of connected components.
**Time:** O(n + E * α(n)), where `E` is the number of connections, `n` is the number of computers, and α(n) is the Inverse Ackermann function. With path compression and union by rank optimizations, the amortized time for each `union` operation is nearly constant (α(n) < 5 for all practical purposes), making the overall time complexity effectively linear, i.e., O(n + E). · **Space:** O(n). The Union-Find data structure requires arrays of size `n` (`parent` and `rank`/`size`), leading to linear space complexity with respect to the number of computers.
**Pros:** Optimal space complexity of O(n).; Very fast, with nearly constant time per operation on average.; Does not require building an explicit graph representation like an adjacency list.
**Cons:** The underlying data structure is more complex to understand and implement from scratch compared to a standard DFS/BFS.
### Explanation
As with the previous approach, we first check if `connections.length < n - 1`. If so, it's impossible, and we return -1.

We then initialize a Union-Find data structure for `n` computers. This structure typically consists of a `parent` array (to track the set representative for each element) and a `rank` or `size` array for optimization. We also maintain a count of the number of components, initially `n`. We iterate through each given connection `[u, v]`. For each connection, we call the `union` operation for `u` and `v`. If `u` and `v` were in different sets, the `union` operation merges them into one set, and our component count is decremented internally. If they were already in the same set, the connection is redundant, and the component count remains unchanged.

After iterating through all connections, the final component count tells us how many separate networks we have. The number of moves needed to connect them is this count minus one.

Here is a Java implementation using a Union-Find class:
```java
class Solution {
    private static class UnionFind {
        private int[] parent;
        private int[] rank;
        private int components;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            components = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]); // Path compression
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                // Union by rank
                if (rank[rootI] > rank[rootJ]) {
                    parent[rootJ] = rootI;
                } else if (rank[rootI] < rank[rootJ]) {
                    parent[rootI] = rootJ;
                } else {
                    parent[rootJ] = rootI;
                    rank[rootI]++;
                }
                components--;
            }
        }
        
        public int getComponents() {
            return components;
        }
    }

    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.getComponents() - 1;
    }
}
```
### Algorithm
- Check if `connections.length < n - 1`. If true, return -1.
- Create a Union-Find (DSU) data structure for `n` computers. Initialize each computer in its own set, and the number of components to `n`.
- Iterate through each `connection` in the `connections` array:
  - Perform a `union` operation on the two computers in the connection. This operation will internally decrement the component count if a merge occurs.
- After the loop, query the Union-Find structure for the final number of components.
- Return `components - 1`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  int makeConnected(int n, int[][] connections) {
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    int cnt = 0;
    for (int[] e : connections) {
      int a = e[0];
      int b = e[1];
      if (find(a) == find(b)) {
        ++cnt;
      } else {
        p[find(a)] = find(b);
        --n;
      }
    }
    return n - 1 > cnt ? -1 : n - 1;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  int makeConnected(int n, vector<vector<int>> &connections) {
    p.resize(n);
    for (int i = 0; i < n; ++i)
      p[i] = i;
    int cnt = 0;
    for (auto &e : connections) {
      int a = e[0], b = e[1];
      if (find(a) == find(b))
        ++cnt;
      else {
        p[find(a)] = find(b);
        --n;
      }
    }
    return n - 1 > cnt ? -1 : n - 1;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] cnt, size = 0, n p = list(range(n)) for a, b in connections: if find(a) == find(b): cnt += 1 else: p[find(a)] = find(b) size -= 1 return - 1 if size - 1 > cnt else size - 1

```