Problem

Submissions

Hints & solutions

Discuss

Queen's Palace

Moderate

0/80

Average time to solve is 25m

Contributed by

5 upvotes

Asked in company

Problem statement

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?

Example:

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 1000
1 <= M <= 2000

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

Explanation for Sample Output 1:

Refer to the image above. The answer can be 1, 3 or 4 as all the states are reachable from these states.

Sample Input 2:

Sample Output 2:

-1

Explanation for Sample Output 2:

As can be seen from the below image:

No node exists such that there will will be a way to all the other nodes from there.

Hint 1

Hint 2

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

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(N * (N + M) ), Where ‘N’ is the number of states and ‘M’ is the number of roads.

Since we are doing a DFS or BFS from all the states. Thus the time complexity will be O(N * (N + M)).

Space Complexity

O(N), Where ‘N’ is the number of states.

Since we are using an array of size N for marking states as visited. Thus the space complexity will be O(N).

(100% EXP penalty)

Queen's Palace

Console