Minimum Operations Required to Make the Network Connected

In this problem, we are given a network of n components. The components are connected to each other, and the information about the connections is given in the form of a 2D array. Our task in this problem is to find the number of minimum extra connections required such that all the components are connected to one of the components of the network. If there is no way that all the components can be connected, then we will return -1.

Examples:

Input: N = 5, c = [[0, 1], [1, 2], [0, 2], [1, 3], [0, 3]]

Output: 1

Input: N = 6, c = [[0, 1], [1, 2], [0, 2], [1, 3], [0, 3]]

Output: 2

Approach - 1

In this problem, we will use the disjoint set to find the number of extra connections in the given network. A disjoint set is a type of data structure. This data structure stores the sets of elements that do not have any element in common. Hence, the name disjoint set. The number of extra connections will tell us the number of new connections that we can make to connect the whole network. If the number of extra connections is less than the number of components - 1, then there is a way to connect the network, and this network will contain n - 1 edges where n is the total number of nodes in the graph. If the condition is not satisfied, then we will return - 1.

We will follow these steps:

• We will make an adjacency list from the given 2D array of connections.
• Then, we will create a disjoint set using the disjoint class and pass the number of components.
• The next step is to check the number of components in the graph. We will find the number of components using the DFS traversal. The number of times the DFS function will called will be equal to the number of components in the graph.
• The last step is to check the condition if the number of components - 1 is less than or equal to the number of extra edges. If yes, then we can connect all the components of the graph.
• The final step is to return the minimum number of edges required.

Below is the implementation of the above approach.

Code

Output:

1

Time Complexity: The DFS takes linear time to traverse through all the nodes of the graph. The operations on the disjoint set work in constant time. Since the total number of nodes is n, the time complexity of this approach is O(n).

Space Complexity: We have used extra space to store the set; therefore, the space complexity of this approach is O (e + n), where e is the number of edges and n is the number of nodes.

Approach - 2

In this approach, we will use the minimum spanning tree method to find the minimum number of connections required to connect the whole network.

Minimum Spanning Tree

Suppose we have an undirected graph. The edges of the graph are weighted. The graph has N number of vertices and E number of edges, and let S be the set containing the edges. A minimum spanning tree is the subset of the set S that contains the edges that are enough to span the complete tree or graph and whose total is the minimum weight of all the possible sets of edges. Thus, a minimum spanning tree contains N - 1 number of edges whose total weight is minimum.

We can use this concept in our problem as we also need N - 1 number of connections to connect the whole network.

Let us see the algorithm of this approach:

• We will start by initializing a map. In Python, we need to create a dictionary object to utilize the features of a map. This dictionary will store the adjacency list of the given network connections.
• We will also create a 2D array of the same size as the adjacency list. We will initialize the array and give 0 value to all the indices. This array will keep track of the visited nodes of the graph, which we will need during the traversal.
• Now, using the information on the connections given to us, we will create the adjacency list of the graph. Using the adjacency list, we can count the number of edges in the graph.
• Now, as we have created the structure of the graph in the form of the adjacency list, we can use the DFS algorithm to traverse the complete graph and count the total number of connected components in the graph.
• Now, we need to calculate the number of extra edges present in the graph. To calculate the number of extra edges, we will use this formula:
  • Extra edges = Total number of edges - [(Total number of nodes - 1) - (Total number of components - 1)]
  • This will give us the count of the edges that we can remove from the graph.
• Now, since the number of connections we can make has an upper limit on the number of connections already present, we need to check if there is a way to connect the network.
• We can check this using the condition
  • Extra edges > Total number of components - 1
  • If this condition is satisfied, then we can connect the disconnected components of the network using these extra edges. The minimum number of edges or connections required to connect the network will be equal to Total number of components - 1.
  • If this condition is not satisfied, then we cannot connect the network with the given number of connections, and hence we will return -1.

Below is the implementation of this approach in Python.

Code

Output:

1

Time Complexity: In this approach, we have used the DFS to find the minimum connections required; hence, the time complexity of this approach is O(n), where n is the number of nodes in the graph.

Space Complexity: We have used extra space to store the array and keep track of the visited nodes. Hence, the space complexity of this approach is O(n).