## Algorithm

Problem Name: 841. Keys and Rooms

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` otherwise.

Example 1:

```Input: rooms = [,,,[]]
Output: true
Explanation:
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],,]
Output: false
Explanation: 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.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
// DFS
class Solution {
public:
bool canVisitAllRooms(vector>& rooms) {
int count = 0, n = rooms.size();
vectorvisited(n);
dfs(rooms, 0, visited, count);
return count == n;
}

void dfs(vector>& rooms, int pos, vector& visited, int& count){
if(visited[pos]) return;
count++;
visited[pos] = 1;
for(auto x: rooms[pos]) dfs(rooms, x, visited, count);
}
};

// BFS
class Solution {
public:
bool canVisitAllRooms(vector>& rooms) {
int count = 0, n = rooms.size();
vectorvisited(n);
queueq;
q.push(0);
while(!q.empty()){
int x = q.front();
q.pop();
if(visited[x]) continue;
visited[x] = 1;
count++;
for(auto neigh: rooms[x]) q.push(neigh);
}
return count == n;
}
};
``````
Copy The Code &

Input

cmd
rooms = [,,,[]]

Output

cmd
true

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean canVisitAllRooms(List> rooms) {
Set visited = new HashSet<>();
while (!queue.isEmpty()) {
int removed = queue.remove();
for (Integer nextRoom : rooms.get(removed)) {
if (!visited.contains(nextRoom)) {
}
}
}
return visited.size() == rooms.size();
}
}
``````
Copy The Code &

Input

cmd
rooms = [,,,[]]

Output

cmd
true

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const canVisitAllRooms = function(rooms) {
const stack = [];
const seen = [];
for (let i = 0; i < rooms.length; i++) {
seen[i] = false;
}
seen = true;
stack.push(0);
while (stack.length) {
let node = stack.pop();
for (let el of rooms[node]) {
if (!seen[el]) {
seen[el] = true;
stack.push(el);
}
}
}
for (let el of seen) {
if (!el) return false;
}
return true;
};
``````
Copy The Code &

Input

cmd
rooms = [[1,3],[3,0,1],,]

Output

cmd
false

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def canVisitAllRooms(self, rooms):
pool, stack = set(range(len(rooms))), 
while stack:
for nex in rooms[stack.pop()]:
if nex in pool:
stack.append(nex)
return not pool
``````
Copy The Code &

Input

cmd
rooms = [,,,[]]

Output

cmd
true

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0841_KeysAndRooms
{
public bool CanVisitAllRooms(IList> rooms)
{
var seen = new HashSet();
var queue = new Queue();
queue.Enqueue(0);

while (queue.Count > 0)
{
var roomId = queue.Dequeue();
foreach (var key in rooms[roomId])
{
if (!seen.Contains(key))
{
queue.Enqueue(key);
}
}
}

return seen.Count == rooms.Count;
}
}
}
``````
Copy The Code &

Input

cmd
rooms = [,,,[]]

Output

cmd
true