Keys and Rooms

Moderate

0/80

Average time to solve is 30m

Contributed by

4 upvotes

Asked in companies

Problem statement

You are given some information about the rooms of a military camp. The rooms are numbered from 0 to 'N-1'. Each room contains keys to some other rooms. You can visit a room only if you have a key to that room. Your task is to determine whether each room can be visited or not.

Note:

1. Room 0 is the only room that is initially unlocked and doesn’t require any key to enter.

2. Any other room can be visited only if you have the key to that room.

3. More than one room can have keys to the same room.

4. You are allowed to visit rooms in any order.

5. You can visit any room multiple times.

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

Input Format:

The first line contains an integer 'T', which denotes the total number of test cases or queries to be run. Then, the 'T' test cases follow. 

The first line of every test case contains an integer 'N', denoting the number of rooms. Then 'N' lines follow.

Each line consists of 'M+1' space-separated integers. The first integer denotes the total number of keys present in this room. The next M integers denote the numbers of the corresponding rooms whose keys are present in this room.

Note that the i-th line denotes information about the keys present in the i-th room.

For more clarity, please refer to the sample inputs.

Output Format:

For each test case, return “True” if it is possible to visit each and every room, otherwise return “False” if it’s not possible.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 5000
1 <= M <= 50
0 <= keys[i] < N

Time Limit: 1sec

Sample Input 1:

Sample Output 1:

False

Explanation for sample input 1:

In the given example, room 0 has keys to room 1 and room 2. So we can go to room 1 and room 2 using these keys. But none of these two rooms has the keys to room 3 and room 4, so we can’t visit room 3 and room 4. Hence, the answer is False.

Sample Input 2:

Sample Output 2:

True

Explanation for sample input 2:

In the given example, room 0 has keys to room 1 and room 2. Room 1 has the key to room 3, and room 3 has the key to room 4. So we can visit each and every room. Hence, the answer is True.

Console