Blueprint

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
0 upvote

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. 
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 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
Sample Input 1 :
2
5 4
0 1
1 2
2 3
0 2
4 2
0 1
0 3
Sample Output 1 :
1
-1
Explanation Of Sample Input 1 :
Test 1:
Remove road between buildings 0 and 3, and add a road between building 0 and 4 , or 1     and 4 ,or 2 and 4 or 3 and 4. 

Test 2:
There are not enough roads to connect all the building in the city, so return -1.
Sample Input 2 :
2
3 2
0 1
1 2
5 4
0 1
1 2
3 4
0 2
Sample Output 2 :
0
1
Hint

Check for the number of connected components.

Approaches (2)
DFS

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.
Time Complexity

O( N + M ), Where ‘N’ is the number of buildings and M is the number of roads. 

 

As for every unmarked building, we are marking all the connected buildings with total M roads.  

 

Hence the time complexity is O( N + M ). 

Space Complexity

O( N + M ), Where ‘N’ is the number of buildings and M is the number of roads. 

 

We are maintaining a visited array of size N. Also, we are creating an adjacency list for storing M*2 road connections.

 

Hence the space complexity is O( N + M ).

Code Solution
(100% EXP penalty)
Blueprint
Full screen
Console