Last Updated: 8 Sep, 2020
Two and Four Wheeler Roads
Hard
Asked in companies
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.
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
Approaches
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.