Ninja And Trains

Hard
0/120
Average time to solve is 60m
profile
Contributed by
6 upvotes
Asked in companies
UberCodenationCapegemini Consulting India Private Limited

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
6 7 3
100 150 68 138 32 22
1 2
2 3
3 4
4 5
5 1
4 6
6 3
4 5 3
100 150 68 62 
1 2
3 4
2 3
4 1
3 1
Sample Output 1:
32
68
Explanation for Sample Output 1:
In the first test case, we can traverse all the node’s values starting from 150 and set them as ‘X’  and check if we remove it will the remaining nodes form a connected component of size at least K. Here we start from 150 and then go to 32. For X= 32, the required conditions are satisfied. For other values of X greater than 32, the conditions are not satisfied, so we return 32 as our answer.

In the second test case, we traverse all the node’s values starting from 150. We can see that if we remove nodes whose values are less than it, then the connected component of size at least 3 is not maintained. So we further decrease X. Finally we reach the value of X = 68, for which given conditions are satisfied. So we return 68 as our answer.
Sample Input 2:
2
4 4 2
3 1 4 5
1 2
2 3
3 4
4 1
5 5 3
3 1 4 5 10
1 2
2 3
3 4
4 1
2 5

##### Sample Output 2: 

1
1
Hint

Can you check for all node values?

Approaches (1)
Kosaraju’s Algorithm

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

O((N + M)logN), where ‘N’ is the number of cities and ‘M’ is the number of trains connecting the cities.

 

As we perform a depth-first search operation, we have the complexity of (V + E), where V is the number of vertices and E is the vertices of the edges. Then we are performing a binary search on the node values, so an additional Log N complexity gets added. Hence, the overall complexity is O( (N + M)  log N).

Space Complexity

O(N + M ), where ‘N’ is the number of cities, and ‘M’ is the number of trains connecting the cities.

 

We store the values in a stack, so the overall time complexity is O(N + M).

Code Solution
(100% EXP penalty)
Ninja And Trains
Full screen
Console