Last Updated: 3 Mar, 2021

Keys and Rooms

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

Approach:

The approach is to view this problem in the form of a graph and use the technique of Depth First Search. For this, we need a recursive function that will take the number of the current room as a parameter. Then, we check whether there is only a single connected component in the graph or not. If the graph is a single connected component, that means all the rooms can be visited. So, the answer is “True” in that case. If it is not a single connected component, then the answer is “False”.

Steps:

Create a boolean array 'IS_VISITED’ of size ‘N’ and initialize all the elements to false initially.
Call the recursive DFS function for room 0 i.e. 'VISIT_ROOMS'(0, rooms, 'IS_VISITED').
Run a loop from ‘i’ = 0 to ‘N’ and do:
if 'IS_VISITED'[i] == false, then return false.
Finally, return true as we are able to visit all the rooms.

void 'VISIT_ROOMS'('CURRENT_ROOM', rooms, 'IS_VISITED') :

Make 'IS_VISITED'['CURRENT_ROOM'] = true.
Run a loop from i=0 to rooms['CURRENT_ROOM'].size and do:
Let key = rooms['CURRENT_ROOM'][i].
If 'IS_VISITED'[key] == false, then we call the function recursively by passing key as the 'CURRENT_ROOM', i.e 'VISIT_ROOMS'(key, rooms, 'IS_VISITED').

Solve now

02 Approach

Approach:

The approach is to view this problem in the form of a graph and use the technique of Breadth-First Search. For this, we need a queue that will allow us to traverse the graph in a Breadth-First Search fashion. Then, we check whether there is only a single connected component in the graph or not. If the graph is a single connected component, that means all the rooms can be visited. So, the answer is “True” in that case. If it is not a single connected component, then the answer is “False”.

Steps:

Create a boolean array “'IS_VISITED'” of size ‘N’ and initialize all the elements to false initially.
Create an empty queue “'TO_BE_VISITED'”.
Push 0 into the queue.
While the queue is not empty, do:
1. Let 'CURRENT_ROOM' = 'TO_BE_VISITED'.front()
2. Pop the front element from the queue. i.e 'TO_BE_VISITED'.pop()
3. Make 'IS_VISITED'['CURRENT_ROOM'] = true.
4. Run a loop from i=0 to rooms['CURRENT_ROOM'].size and do:
  1. Let key = rooms['CURRENT_ROOM'][i]
  2. If 'IS_VISITED'[key] == false, then push key into the queue.
Run a loop from ‘i’ =0 to ‘N’ and do:
1. if 'IS_VISITED'[i] == false, then return false.
Finally, return true as we are able to visit all the rooms.

Solve now

03 Approach

Approach:

The approach is to view this problem in the form of a graph and use the technique of Depth First Search iteratively and keep a count of the visited 'ROOMS'. For this, we need a stack that will allow us to traverse the graph in a Depth First Search fashion. Then, we check whether the count of the visited 'ROOMS' is equal to the total number of 'ROOMS' or not. If the count is equal, that means all the 'ROOMS' can be visited. So, the answer is “True” in that case. If it is unequal, then the answer is “False”.

Steps:

Create a boolean array “IS_VISITED” of size N and initialize all the elements to false initially.
Create an empty stack “TO_BE_VISITED” and push 0 into the stack.
Create a variable called 'ROOMS_VISITED', which keeps track of the number of rooms visited so far and initialize it to 1, as we are already present in room 0.
Make IS_VISITED[0] = true.
While the stack is not empty, do :
1. Let 'CURRENT_ROOM' = 'TO_BE_VISITED'.top()
2. Pop the top element from the stack. i.e 'TO_BE_VISITED'.pop()
3. Run a loop from i=0 to 'ROOMS'['CURRENT_ROOM'].size and do :
  1. Let key = 'ROOMS'['CURRENT_ROOM'][i]
  2. If IS_VISITED[key] == false,
    1. push ‘key’ to the stack.
    2. Make IS_VISITED[key] = true.
    3. Increase the number of 'ROOMS' visited by 1. i.e., 'ROOMS_VISITED'++.
Finally, if 'ROOMS_VISITED' == 'TOTAL_ROOMS', return true. Else, return false.

Solve now