Last Updated: 8 Sep, 2022

Blueprint

Moderate

Solve now

Problem statement

Sam is updating the blueprint of a city. The original blueprint of the city consists of ‘N’ buildings numbered from 0 to ‘N’-1 which are connected by ‘M’ roads, ‘CONNECTIONS’ forming a network where CONNECTIONS[i] = [‘Ai’,’Bi’] represents a road between buildings ‘Ai’ and ‘Bi’.

Any building can be reached from any other building directly or indirectly connected through a series of roads.

There could be some buildings in the original blueprint of the city which are not connected with some other buildings directly or indirectly. Sam wants to update the blueprint of the city by removing some roads which directly connected any two buildings and adding a road between two disconnected buildings to make them connected.

Return the minimum number of times Sam needs to perform the changes such that all the buildings can be reached from any other building through a series of roads. If it is not possible, Return -1.

Example:

Input: ‘N’ = 5 , ‘M’ = 4 ,   'CONNECTIONS' =  [[0,1],[1,2],[2,3],[0,3]]

Output: 1
Explanation:
Remove the road between buildings 0 and 3, and add a road between buildings 0 and 4 , or 1 and 4 ,or 2 and 4 or 3 and 4.

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 integers, 'N’ and ‘M’, denoting the number of buildings and number of connections..

The next ‘M’ lines of each test case contains pair of two integers, denoting the road between buildings.

Output format :

Return an integer, denoting the minimum changes Sam needs to perform in the blueprint.

Constraints :

1  <= T <= 10
1  <= N <= 100000
1 <= M <= min(N x (N-1)/2 , 100000)
CONNECTIONS[i].length == 2
0 <= Ai,Bi < N
Ai != Bi
There are no repeated connections.
No two buildings are connected by more than one road. 
Time Limit: 1 sec

Solve now

Approaches

01 Approach

The solution to the problem lies in counting the number of connected components.

We will make an adjacency list for undirected graph ‘adj’ using the ‘CONNECTIONS’, then if the number of roads is less than ‘N’-1, then the answer is not possible so return -1.

Now make a visited array, we run a loop for all buildings and if the current building is not marked in the visited array we will run a DFS for this building the mark all the connected buildings, and similarly, we will store the number of times we need to run a DFS in a counter, which is nothing but the number of connected components.

The DFS part can be implemented recursively or iteratively using a stack.

The steps are as follows :

Function DFS( int currentEle, adj[int][int] )

Mark the visited array for the current element, ‘currentEle’.
For all unvisited ‘nextElement’ in the adjacency list,adj[currentEle]
- Call DFS for the nextElement

Function connetedComp (int N,int M,CONNECTIONS[int][] )

If M is less than N-1,
- Return -1.
Create adjacency list ‘adj’ considering an undirected graph.
For ‘idx’ in range 0 to N-1
- If idx is not marked in the visited array
  - Counter = counter+1.
  - Call DFS for idx.
Return counter-1.

Solve now

02 Approach

The solution to the problem lies in counting the number of connected components.

If the number of roads is less than ‘N’-1, then the answer is not possible so return -1.

Now we will make a data structure, Disjoint Set Union using which we will find the number of connected components, ‘counter’ and return counter-1.

The DSU part (Union by Size) can be implemented following the steps below.

The steps are as follows :

Function makeSet(int element,parent[int])

Assign the parent of the element to itself initially.

Function findSet(int element,parent[int])

If the parent of the element is storing the element itself
- Return element.
Return value assigned to the parent of the element by recursively calling findSet.

Function unionSet(int element1,int element2,parent[int],size[int])

Assign parent1 with findSet(element1,parent,size).
Assign parent2 with findSet(element2,parent,size).
If parent1 and parent2 are not the same
- Swap parent1 and parent2 if the size of parent1 is less than parent2.
- Change parent of parent2 to parent1.
- Add size of parent2 to size of parent1.

Function connectedComp(int N,int M,CONNECTIONS[int][])

Initialize two arrays parent and size of length N.
If M < N-1
- Return -1.
For ‘idx’ in range 0 to N-1
- Make set for all idx.
For ‘idx’ in range 0 to M-1
- Union of CONNECTIONS[i][0] and CONNECTIONS[i][1].
Assign counter to 0.
For ‘idx’ in range 0 to N-1
- If parent and idx are the same
  - Add 1 to the counter.
Return counter-1.

Solve now