Queen's Palace

Posted: 25 Dec, 2020
Difficulty: Moderate


Try Problem

Ninjaland is a country having 'N' states numbered from 1 to 'N'. These 'N' states are connected by 'M' uni-directional roads. As the roads are directional, it may be a case that some states are not reachable from one state even if they are connected. But the queen of the Ninjaland wants to live in a state from where she can reach all the other states.

Can you find such a state where the queen can have her palace?

Let’s take an example for the below given Ninjaland.


For the given example, the states from which we can reach all other states are 1, 3, 4. So, you can answer any one of them.
Input format :
The first line contains an integer 'T' denoting the number of test cases. 

The first line of each test case contains two space-separated integers 'N' and ‘M’ representing the number of states and number of roads in the country, respectively. 

The next 'M' lines of every test case contain two single space-separated integers ‘A’ and ‘B’, representing a road between the states 'A', 'B' and directed from state 'A' to state 'B'.
Output format:
For each test case, return a single integer denoting the state in which the queen should live. If there is no state from which the queen can reach all other states then return -1.
You don't need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 100
1 <= N <= 1000
1 <= M <= 2000

Time limit: 1 sec
Approach 1

The very first approach can be to try all states and check if we can reach all other states from the current state.


The steps are as follows:


  • Select each state for the queen.
  • Try to visit all possible states from the selected state using a DFS or BFS.
  • If the count of visited states is equal to the total number of states then the queen can live in the selected state.
Try Problem