Two and Four Wheeler Roads

Hard
0/120
Average time to solve is 48m
profile
Contributed by
15 upvotes
Asked in companies
Wells FargoGoldman SachsGartner

Problem statement

There is a country with 'N' cities and 'M' bidirectional roads of 3 types.

Type 1: Two Wheeler Road, It means only vehicles having two wheels can use this road.
Type 2: Four Wheeler Road, It means only vehicles having four wheels can use this road.
Type 3: Both two and four Wheeler Road, It means this road can be used by both type of vehicles.

The problem is to find the maximum number of roads that can be removed such that a path exists for every pair of cities for each two-wheeler and four-wheeler vehicle.

Note: 
1. Roads may form a cycle.

2. The cities do not have multiple same roads i.e all the roads are unique.

3. If every city cannot be reached, then return -1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an Integer 'T' which denotes the number of test cases.

The first line of each test case contains 2 space-separated integers: 'N' and 'M', Where 'N' denotes the number of cities and 'M' denotes the number of roads as described below.

Each of the following 'M' lines contains 3 space-separated integers x,y, and z. It describes a bi-directional road of type z between the cities x and y.
Output Format: 
For each test case, print the maximum number of roads that can be removed such that a path exists for every pair of cities for each two-wheeler and four-wheeler vehicle.
Note: 
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 10^3
1 <= M <= min(100000,(N*(N-1))/2)
1 <= x,y <= N
1 <= z <= 3

Time limit: 1 sec
Sample Input 1:
2
4 6
3 4 2
2 3 3
1 2 3
2 4 1
1 2 1
1 3 1
10 1
1 2 3
Sample Output 1:
2
-1
Explanation of the Sample Output 1:
In test case 1, If we remove the road between cities 1 and 2 of type 1 and also the road between the cities 1 and 3 of type 1 still we can reach any city from any other city and this holds true for both type of vehicles.

In test case 2, There are 10 cities and there is only one road between cities 1 and 2 of type 3. So we can not reach every city from any other city.
Sample Input 2:
2
2 1
1 2 3
4 6
1 2 1
1 3 2
1 4 3
3 4 1
2 3 1
2 4 2
Sample Output 2:
0
1
Explanation of the Sample Output 2:
In test case 1, There is only one road two wheeler road and one four wheeler road, and thus no road can be removed.

In test case 2, If we remove the road between city 2 and city 3 of type 1, still we can reach any city from any other city and this holds true for both type of vehicles.
Hint

Think greedily, that is type 3 is beneficial for us so use this as much as possible and then use type 1 and type 2 and remove the rest roads.

Approaches (1)
Optimal Approach

We will create the 3 separate graphs.

 

  • ‘Graph1’: The first graph will be build using the roads of type 1 and type 3.
  • ‘Graph2’: The second graph will be build using the roads of type 2 and type3.
  • 'Graph3': This graph will be build using the roads of type 3 only.

 

We will have a ‘DFS’ function that will return the number of cities which are reachable from starting city and also helps to know the connectivity of the the 'Graph1' and ‘Graph2’. Do a ‘DFS’ from city 1 in 'Graph1' if the number of reachable cities is less than ‘N’, it means we can not reach every city starting from any other cities so print -1 and return. Similarly, do this for ‘Graph2’. Now that we have checked the connectivity of both graphs, we can remove redundant roads.

 

Declare and Initialize a variable ‘usedRoads’ as 0, where ‘usedRoads’ will store the count of used roads during a iterative check. Find the number of the connected component in Graph3 using the same ‘DFS’ function. Run a loop from i = 1 to ‘N’ and if the ‘i’th city is not visited perform a ’DFS' starting from this city which will return the number of reachable cities. If there are X cities reachable then we will only need X-1 roads so usedRoads+=(X-1). At the same time count the number of connected components. 


Let’s say we have ‘COMPONENT’ number of connected components. So we will need ‘COMPONENT’ -1 roads of type 1 and ‘COMPONENT’ - 1 roads of type 2. So add (2 * (‘COMPONENT’ - 1)) to the ‘usedRoads’. We can now remove ‘usedRoads’ from ‘M’ and store it in ‘RESULT’ and return it.

Time Complexity

O(V + E), where ‘V’ is the number of cities and ‘E’ is the number of roads.

 

Since we are performing the DFS which takes O(V + E) time complexity as it visits every node as well as every edge and thus the time complexity will be O(V + E)..

Space Complexity

O(V + E), where ‘V’ is the number of cities and ‘E’ is the number of roads.

 

 Since we are using adjacency lists to store a graph, we require O(V + E) space and thus space complexity will be O(V + E).

Code Solution
(100% EXP penalty)
Two and Four Wheeler Roads
Full screen
Console