Number Of Operations To Make Network Connected - Leetcode Solution

Problem Statement:

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.

Solution:

To solve this problem, first, we need to understand the concept of a disconnected graph and connected components of a graph. A graph is said to be disconnected if there are two or more vertices that are not connected by any edge. On the other hand, a connected component is a subgraph in which every two vertices are connected to each other by a path.

Approach:

1. Create the adjacency matrix for the given connections.
2. Count the number of connected components in the graph using DFS or BFS algorithms.
3. If there is only one connected component, the given graph is already connected, so return 0.
4. Otherwise, the number of cables that need to be added is equal to the number of connected components minus 1.

Pseudo code:

1. def makeConnected(n: int, connections: List[List[int]]) -> int:

2. graph = [] # to store the edges
   

3. for i in range(n):
   

4.     graph.append([])
   

5. for i in range(len(connections)):
   

6.     a = connections[i][0]
   

7.     b = connections[i][1]
   

8.     graph[a].append(b)
   

9.     graph[b].append(a)
   

11. visited = [False] * n
    

12. components = 0
    

13. for i in range(n):
    

14.     if not visited[i]:
    

15.         dfs(graph, visited, i)
    

16.         components += 1
    

17. if len(connections) < n-1:
    

18.     return -1
    

19. else:
    

20.     return components -1
    

22. def dfs(graph, visited, i):

23. visited[i] = True
    

24. for j in range(len(graph[i])):
    

25.     if not visited[graph[i][j]]:
    

26.         dfs(graph, visited, graph[i][j])
    

Time complexity:

We need to iterate over the connections for creating an adjacency list and perform a DFS or BFS traversal over the graph, hence the overall time complexity is O(N+E).

Space complexity:

We use an adjacency list and visited array to keep track of visited nodes in DFS, which requires O(N+E) space.

Conclusion:

In this problem, we have learned how to count the number of operations required to make a disconnected graph connected. We have used DFS algorithm here, and our solution has a time complexity of O(N+E) and space complexity of O(N+E).

1