Minimum Connection Changes

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
7 upvotes
Asked in companies
OlaMeeshoDXC Technology

Problem statement

In an internet cafe, there are 'N' computers numbered from 1 to ‘N’. These computers are connected by 'M' wires. Each wire connects two different computers. Information can be transmitted between two computers if there exists a path between the two computers by travelling through some ( possibly Zero ) intermediate computers. The cafe owner wants to remove some of the existing wires and then use those wires to connect some other pair of computers in such a manner that after the rearrangement, it is possible to transmit information between all the pairs of computers.

You are given the description of each of the 'M' wires, i.e., the two computers that the wire connects. Your task is to find the minimum number of wires that the cafe owner needs to remove and rearrange to satisfy the above conditions.

If there is no possible way to remove and rearrange wires to satisfy the above conditions, then return -1.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, 'N' and 'M', denoting the number of computers and the number of wires, respectively.

The next 'M' lines of each test case contain the description of the 'M' wires

The 'i'th' line contains two space-separated integers, 'Computer1', and  'Computer2' . 'Computer1'' and 'Computer2' denote the two computers that are connected by the 'i'th' wire.
Output Format : 
The only line of output of each test case should contain the minimum number of wires that should be removed and rearranged so that it is possible to transmit information between all pairs of computers.

Print the output of each test case in a new line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
0 <= M  <= min(10^5, (N*(N-1))/2)
1 <= Computer1, Computer2 <= N

Any two computers are directly connected by at most one wire.

Time Limit: 1 sec
Sample Input 1 :
2
4 3
1 2
1 3
2 3
4 2
1 2
3 4
Sample Output 1 :
1
-1
Explanation For Sample Input 1 :
For the first test case :  
We can remove the wire that connects Computer 1 and Computer 3, and use that wire to connect Computer 1 and Computer 4. Now, all the computers are connected. Hence, the answer is 1 in this case.

input

For the second test case:

input 

For the above network, we can see that it is impossible to replace the wires so that information can be transmitted between all computers. Hence, the answer is -1 in this case.
Sample Input 2 :
2
4 4
1 2  
3 1
2 3
3 4  
4 3
3 4
3 2
2 4
Sample Output 2 :
0
1
Hint

Try to think of remodelling the problem as a graph problem. 

Approaches (2)
DFS Approach

Let us first find the condition for which it is impossible to replace wires to connect all computers. The only necessary and sufficient condition to check is that the number of wires should always be greater than or equal to the number of computers - 1, i.e., M > = ( N - 1 ). If this condition holds true, then the answer can never be -1. Otherwise, the answer will always be -1. This condition is necessary because to form a connected network of computers using minimum wires, we need to form a tree-like structure, and the number of edges in a tree having N nodes is N - 1.

 

Now we will remodel the above problem as a graph problem. The computers will act as the graph vertices, and the wires will act as the graph edges. The problem now reduces to find the number of connected components in the graph. If the number of connected components in the graph is K, then our answer will be K - 1. This works because here, a connected component represents a network of computers that can transmit information among them. We already have checked that there are sufficient wires available, so we can take a wire from a connected component having an extra wire and use it to connect to another component to make a bigger connected component. We will need to do this step until all the connected components are not joined together. If we simulate the above process for some small graphs. We can observe that our answer will always be numberOfConnectedComponents - 1.

 

We can find the connected components and the number of connected components in a graph using Depth-First search (DFS). Reference.  

 

Algorithm

 

  • If N - 1 is greater than M, then we will return -1 as it will be impossible to make all the computers connected.
  • Create an empty graph having N + 1 nodes.
  • Iterate through the list of wires and add corresponding edges in the graph.
  • Let’s define a “visited” array of size N+1 to store each node’s visit status.
  • Initialize numberOfConnectedComponents variable to 0.
  • Iterate from i = 1 to N 
    • If visited[i] is equal to 0, then increase numberOfConnectedComponents by 1 and do a Depth-First Search on the i’th node and mark all the nodes connected to it as visited.
  • Return the final answer, i.e, numberOfConnectedComponents - 1.
Time Complexity

O(N+M), where ‘N’ denotes the number of computers, and ‘M’ denotes the number of wires.

 

As we are using DFS to find the number of connected components in the graph, and we will visit each edge of the graph exactly once, hence the time complexity of doing that will be O(M). We also need to create and traverse the visited array for DFS having N elements. Hence, the overall time complexity is O(N+M). 

Space Complexity

O(N+M), where ‘N’ denotes the number of computers, and ‘M’ denotes the number of wires.

 

The visited array required for DFS has N elements, and the number of edges in the built graph is M. Hence, the overall space complexity is O(N+M).

Code Solution
(100% EXP penalty)
Minimum Connection Changes
Full screen
Console