> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/number-of-operations-to-make-network-connected.md).

# Number of Operations to Make Network Connected

There are `n` computers numbered from `0` to `n-1` connected by ethernet cables `connections` forming a network where `connections[i] = [a, b]` represents a connection between computers `a` and `b`. Any computer can reach any other computer directly or indirectly through the network.

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's not possible, return -1. 

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/01/02/sample_1_1677.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.leetcode.com/uploads/2020/01/02/sample_2_1677.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.
```

**Example 4:**

```
Input: n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
Output: 0
```

**Constraints:**

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

```java
class Solution {
    public int makeConnected(int n, int[][] connections) {
        // Graph creation
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        for (int[] edge : connections) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        // Finding number of connected components
        // In our undirected graph
        boolean[] visited = new boolean[n];
        int cablesUsed = 0, components = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                cablesUsed += DFS(graph, i, visited);
                components++;
            }
        }
        int cablesNeeded = components - 1;
        return (connections.length - cablesUsed) >= cablesNeeded ? cablesNeeded : -1;
    }

    public int DFS(List<Integer>[] graph, int i, boolean[] visited) {
        visited[i] = true;
        int count = 0;
        for (int x : graph[i])
            if (!visited[x])
                count += DFS(graph, x, visited) + 1;
                
        return count;
    }
}
```