Last Updated: 10 Jul, 2021
Ninja And Trains
Hard
Asked in companies
Ninja is given a few cities and few connected Trains. Each city has a specific size. Now due to bad weather, trains from certain cities get canceled. Given a value X, if the size of the city is less than X, then all incoming and outgoing trains from the station get canceled. Now Ninja’s task is to determine the maximum threshold value X such that trains from cities with a size less than X gets canceled, then there should exist a reachable component of cities in the network of size at least K. A subcomponent of the city network is considered to be a reachable component if all the cities in that network are connected, which implies all the trains are available from each other via direct or connecting trains.
Input Format:
The first line of input contains a single integer T, denoting the number of test cases.
The first line of each test case contains ‘N’, denoting the number of cities, ‘M’ denoting the number of trains, and ‘K’ denoting the size of the connected network of cities.
The second line of each test case contains 'N' space-separated integers denoting the value associated with the i-th city.
The next 'M' lines of each test case contains ‘M’ pairs (u, v), denoting a train available from city u to city v.
Output Format :
The first and only line of each test case contains the maximum threshold value X, if the maximum threshold value is infinite the return 10 ^ 9. If there is no connected network of cities of size at least K, then return -1.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 5
1 <= k <= N <= 10^5
1 <= M <= 10^5
1 <= value of nodes <= 10 ^ 9
Time limit: 2 second
Approaches
We can select a value of k from 10^9 to 1 using Binary search, and then using this k value, and we can check that if nodes with values less than K are removed, we see how many connected components are left. If the number of related components is greater than X, it means that this value is suitable for K. If the number of connected components is less than K, then we have decreased the value of K. If at some point while decreasing K by using Binary search if for a particular value of K the number of connected components is more than X then we can ignore the left part and do a binary search on the right side only. To find the number of related components in a graph, we are using Kosaraju’s algorithm, where we do DFS on the nodes and find a list of all those nodes which can be reached from all other nodes. A graph is strongly connected if there is a path between all pairs of vertices.
The steps are as follows:
- Initialize ‘l’ as the lower limit for binary search and ‘r’ as the upper limit for binary search, and ‘ans’ to store the value of the maximum ‘K’.
- We run a while loop as long as l is less than equals r:
- Initialize ‘mid’ as (l + r)/2.
- We pass mid, u denoting the start of an edge, v denoting end of an edge, X denoting a maximum number of connected components after removing specific nodes, array denoting the node values to function check which returns true if the chosen value for K satisfies all the given conditions inside the function check which returns true if all conditions satisfied else returns false.
- We initialize a ‘visited’ vector’ to store all the nodes that are visited.
- We initialize an empty stack ‘ssc’ to store the node values.
- We initialize a vector ‘graph’ to map the edges.
- We run a loop from i = 0 to i = M:
- We initialize a with u[i] and b with v[i]
- If array[a-1] greater than equals X and array[b-1] greater than equals X, then push in graph[a-1] the value (b -1) because if the node and its child’s value is greater than K, then it will be part of the connected component
- We run a loop from i = 0 to i = N - 1:
- If the node is not yet visited, pass i to the dfs function, which performs DFS on the nodes.
- We initialize visit[node] with 1 to mark this node has been visited.
- We run a loop from i = 0 to i = graph[node].size:
- If the child nodes of the current node are not visited, mark that node as visited and perform dfs on that node.
- Push the current node in the stack.
- We clear the vectors ‘graph’ and ‘visited’.
- We run a loop from i = 0 to i = M:
- We initialize a with u[i] and b with v[i]
- If array[a-1] greater than equals X and array[b-1] greater than equals X then push in graph[b-1] the value (a -1).
- While the stack ‘ssc’ is not empty, we pop one element and check if the value denoting node value is visited or not. If it is already visited, then continue popping.
- Else increment count, which keeps count of connected components.
- We then pass the current node value to dfs2, which helps to traverse the tree.
- We increment size[count] by 1.
- We run a loop from i = 0 to i = graph[node].size():
- If the child nodes of the current node are not visited, then mark that node as visited and perform dfs on that node else continue.
- We run a for loop from i =1 to i less than equal count:
- We store in ‘ans’ max of ‘ans’ and ‘size and store 0 in size[i].
- If ans is greater than ‘X’ then return true else, return false.
- If it returns true, then store mid in ‘ans’ and mid + 1 in ‘l’.
- Else store mid - 1 in ‘ans’.
- Finally, return ‘ans’ as our answer.
Similar problems