There are `n`

rooms labeled from `0`

to `n - 1`

and all the rooms are locked except for room `0`

. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of **distinct keys** in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array `rooms`

where `rooms[i]`

is the set of keys that you can obtain if you visited room `i`

, return `true`

*if you can visit all the rooms, or*

`false`

**Example 1:**

Input:rooms = [[1],[2],[3],[]]Output:trueExplanation:We visit room 0 and pick up key 1. We then visit room 1 and pick up key 2. We then visit room 2 and pick up key 3. We then visit room 3. Since we were able to visit every room, we return true.

**Example 2:**

Input:rooms = [[1,3],[3,0,1],[2],[0]]Output:falseExplanation:We can not enter room number 2 since the only key that unlocks it is in that room.

**Constraints:**

`n == rooms.length`

`2 <= n <= 1000`

`0 <= rooms[i].length <= 1000`

`1 <= sum(rooms[i].length) <= 3000`

`0 <= rooms[i][j] < n`

- All the values of
`rooms[i]`

are**unique**.

The description was taken from https://leetcode.com/problems/keys-and-rooms/.

`#DFS`

#O(N) Time, O(N) Space

**class** **Solution**:

**def** **canVisitAllRooms**(self, rooms: List[List[int]]) -> bool:

seen = {}

**def** **dfs**(room:int) -> None:

**if** room **in** seen:

**return**

seen[room] = True

**for** key **in** rooms[room]:

**if** key **not** **in** seen:

dfs(key)

dfs(**0**)

**return** len(seen) == len(rooms)

`#BFS`

#O(N) Time, O(N) Space

**class** **Solution**:

**def** **canVisitAllRooms**(self, rooms: List[List[int]]) -> bool:

seen = {}

**def** **bfs**(room:int) -> None:

queue = collections.deque([(**0**)])

**while** queue:

room = queue.popleft()

seen[room] = True

**for** key **in** rooms[room]:

**if** key **not** **in** seen:

queue.append((key))

bfs(**0**)

**return** len(seen) == len(rooms)

To solve this problem, we can visit the first room, grab its set of keys and visit the corresponding rooms.

We will then continue that process on each room we have keys for until we have not received any more keys.

At that point, we will see if the number of rooms that we had seen is equal to the number of rooms that were given.

Let's start by initializing the dictionary for seen rooms.

` seen = {}`

Next, we will build our recursive, DFS function that will be run on a given room.

` `

**def** **dfs**(room:int) -> None:

If the room has already been seen, then we will return because we already have the keys for it.

` `

**if** room **in** seen:

**return**

Otherwise, we will mark the room as seen, grab each key that we have in the room, and if we have not yet seen a room for each corresponding key, we will visit the room next.

` seen[room] = True`

**for** key **in** rooms[room]:

**if** key **not** **in** seen:

dfs(key)

Now that we have our DFS function built, we will begin visiting the first room's set of rooms.

` dfs(`

**0**)

After our DFS has been completed, we will return whether we visited all of the rooms by comparing the number of rooms we had seen.

` `

**return** len(seen) == len(rooms)

For the BFS version, the only difference is we'll just need to swap out a queue for our recursive call stack.

` `

**def** **bfs**(room:int) -> None:

queue = collections.deque([(**0**)])

**while** queue:

room = queue.popleft()

seen[room] = True

**for** key **in** rooms[room]:

**if** key **not** **in** seen:

queue.append((key))