Rooms

Posted: 3 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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:

 

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

 

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

  1. Make 'IS_VISITED'['CURRENT_ROOM'] = true.
  2. 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 we call the function recursively by passing key as the 'CURRENT_ROOM', i.e 'VISIT_ROOMS'(key, rooms, 'IS_VISITED').
Try Problem