Last Updated: 5 Apr, 2021
Number of operations to make Graph connected.
Easy
Asked in companies
You have been given a graph consisting of ‘N’ vertices numbered from 1 to ‘N’. The graph has ‘M’ edges. In an operation, you can shift an edge between two directly connected vertices to between pair of disconnected vertices to make them directly connected. Return the minimum number of operations to make the graph connected. If it is not possible to make graph connected return -1.
Example:
Let’s say ‘N’ is 4 and ‘M' is 3. The 3 edges are (1,2), (2,3) and (1,3). Then our graph will look as follows:-
To make the graph connected we can shift the edge between (1,3) to (1,4). This operation will make the graph connected. There are multiple ways in which we can make graph connected. So, in this case, we can make graph connected in just one operation.
Note:
1. A connected graph is a graph that is connected in the sense of a topological space, i.e., there is a path from any vertex to any other vertex in the graph.
2. There are no repeated edges and self-loops in the graph.
3. You do not need to print anything; it has already been taken care of. Just implement the function.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the number of vertices and the number of edges in the graph.
Each of the next ‘M’ lines contains two space-separated integers representing the vertices that are directly connected by an edge.
Output Format:
For each test case, print a single line containing a single integer denoting the minimum number of operations to make the graph connected. If it is not possible to make graph connected return -1.
The output of each test case will be printed in a separate line.
Note:
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10000
1 <= M <= 10000
1 <= U[i], V[i] <= N
Where ‘T’ is the number of test cases.‘N’ is the number of vertices in the graph. ‘M’ is the number of edges in the graph. ‘U[i]’ and ‘V[i]’ are vertices of the i-th edge.
Time Limit: 1sec.
Approaches
For a graph with ‘N’ vertices to be connected, there must be at least ‘N’ - 1 edges in the graph. If a graph has less than ‘N' - 1 edges it is impossible to make the graph connected. Otherwise, it is always possible to make graph connected. As we need to find the minimum number of operations to make the graph connected we will think greedily. We will find the total number of connected components in the graph. We can treat each connected component in the graph as a single vertex. Basically, we want to shift edges such that these components become connected. Therefore answer will be the total number of connected components - 1.
We will apply the algorithm as follows:-
- If ‘m’ is less than ‘N’ - 1 return -1.
- Declare a list of list/vector ‘adj’ of size ‘N’ + 1 where ‘adj[i]’ stores vertices that are directly connected to node ‘i’.
- Iterate ‘i’ from ‘1’ to ‘m’:-
- Therefore push ‘v[i]’ in ‘adj[u[i]]’ and ‘u[i]’ in ‘adj[v[i]]’.
- Maintain an auxiliary array ‘vis’ which maintains if ‘i-th’ vertex has been visited.
- Declare ‘ctr’ and initialize it with ‘0’. It stores the number of connected components.
- Iterate ‘i’ from ‘1’ to ‘N’:-
- If node ‘i’ has not been visited yet:-
- Mark node ‘i’ as visited and insert it in the queue.
- Increase ‘ctr’ by ‘1’ as it is a new component.
- Iterate till the queue is empty:-
- Pop the front element of ‘q’ and store it in ‘u’.
- Iterate over ‘adj[u]’
- If the ‘adjacentNode’ is not visited yet. Mark ‘vis[adjacentNode]’ as true and insert ‘adjacentNode’ in queue.
- If node ‘i’ has not been visited yet:-
- Declare ‘ans’ and initialize it with ‘ctr’ - 1.
- Return ‘ans’.
For a graph with ‘n’ vertices to be connected, there must be at least ‘N’-1 edges in the graph. If a graph has less than ‘N’-1 edges it is impossible to make the graph connected. Otherwise, it is always possible to make graph connected. As we need to find the minimum number of operations to make the graph connected we will think greedily. We will find the total number of connected components in the graph. We can treat each connected component in the graph as a single vertex. Basically, we want to shift edges such that these components become connected. Therefore answer will be the total number of connected components - 1. We can find the total number of connected components using disjoint set union.
We will apply the algorithm as follows:-
- If ‘M’ is less than ‘N’-1 return -1.
- Declare a list of ‘parent’ and ‘s’ of size ‘N’+1.
- In Disjoint Set Union there are two main functions i.e dsunion() and root():-
- root() - Recursively determine the topmost parent of a given vertex.
- dsunion() - Connects two vertices by an edge.
- Iterate ‘i’ from ‘1’ to ‘N’:-
- Initialize ‘parent[i]’ with ‘i’ and ‘s’ with ‘1’.
- Declare ‘ans’ and initialize it with ‘N’ which signifies the number of connected components in the graph. Till now no edge has been added, therefore the number of connected components is ‘N’.
- Iterate ‘i’ from ‘1’ to ‘M’:-
- Check if root(u[i])!=root(v[i]) i.e. whether u[i] & v[i] are part of different connected component. If they are part of different connected component:-
- We will connect these two vertices using ‘dsunion(u[i],v[i])’.
- We will decrease the total number of connected components i.e. ‘ans’ by 1 because when we add connect edge between u[i] and v[i] the two components they are part of becomes a single component.
- Check if root(u[i])!=root(v[i]) i.e. whether u[i] & v[i] are part of different connected component. If they are part of different connected component:-
- Return ‘ans’ - 1 because ‘ans’ stores the total number of connected components.