Minimum Connection Changes

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.

The basic idea of this approach is to use a Disjoint Set Union data structure to find the number of connected components in the graph. We have seen in approach 1 that the problem is finally reduced to finding the number of connected components in an undirected graph. So we can use DSU to do this task very efficiently. We will use the union by size for optimisation. 

Algorithm

• If N - 1 is greater than M, then we will return -1 as it will be impossible to make all the computers connected.
• Let’s define a “parent” array of size N+1 to store the parent node of each node from 1 to N.
• 3.  Create a DSU data structure and initialize it using makeSet( ), in which we will initialize the parent node of each node to itself.
• Let’s define two functions findParent and unionSets, to find the parent node of a particular node and to merge two components of the graph, respectively.   
• Initialize the variable numberOfConnectedComponents as N to store the number of connected components in the graph as initially no two nodes are connected. Now whenever we will merge two sets, we will decrease our answer by 1.
• Iterate through each the list of wires
  • Let computer1 and computer2 denote the two computers connected by this wire.
  • If findParent(computer1) is not equal to findParent(computer2), then decrease numberOfConnectedComponents by 1 and call unionSets(computer1,computer2). We are decreasing our answer by 1 as the two components to which computer1 and computer2 belong are already the same. So we do not need to connect them.
• Return the final answer, i.e, numberOfConnectedComponents - 1.