Components of Graph <Airbus>

4.2

5 votes
Algorithms, Binary Search, Graphs, Hard, Strongly Connected Components
Problem

You are given a directed network of flights i.e. N cities and M one-directional flights. Each city has a particular air quality index value associated with it. Now, your task is to determine the maximum threshold value X such that if the flights incident to or from the cities with air quality index values less than X is canceled then there should exist a reachable component of cities in the network of size at least K. A subcomponent of a flight network is considered to be a reachable component if all the cities in that component are connected, this implies that all the flights are reachable from each other via direct or connecting flights.
Note: You can assume that the answer always exists.

Input format

  • First line: Three integers N, M, and K
  • Next line: N space-separated integers where the ith integer denotes the value associated with the city number i
  • Next M lines: Two space-separated integers u and v that denote that there is a flight available from the city number u to v

Output format
Print the maximum threshold value as described in the problem statement.

Constraints
1KN105
1M106
1valueofnodes109

Sample Input
6 7 3
100 150 68 138 32 22
1 2
2 3
3 4
4 5
5 1
4 6
6 3
Sample Output
32
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

If you keep the threshold as 32 then you see that there exists a component of size 5 which is greater than 3 and follows the given property.

Editor Image

?