> For the complete documentation index, see [llms.txt](https://dongzeli95s-organization.gitbook.io/swe-interview-handbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dongzeli95s-organization.gitbook.io/swe-interview-handbook/algorithm/dfs/keys_and_rooms.md).

# Keys And Rooms

````cpp
// https://leetcode.com/problems/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.

Ex1:
Input: rooms = [[1],[2],[3],[]]
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.

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

*/

#include <vector>
#include <cassert>
#include <unordered_set>

using namespace std;

// N is number of rooms, E is number of keys
// Time: O(N+E), Space: O(N)
void dfs(int curr, vector<vector<int>>& rooms, unordered_set<int>& visited) {
    for (int next: rooms[curr]) {
        if (visited.count(next)) continue;
        visited.insert(next);
        dfs(next, rooms, visited);
    }
}

bool canVisitAllRooms(vector<vector<int>>& rooms) {
    int n = rooms.size();
    unordered_set<int> visited;
    visited.insert(0);
    dfs(0, rooms, visited);

    return visited.size() == n;
}

int main() {
    vector<vector<int>> rooms1 = {{1},{2},{3},{}};
    assert(canVisitAllRooms(rooms1) == true);

    vector<vector<int>> rooms2 = {{1,3},{3,0,1},{2},{0}};
    assert(canVisitAllRooms(rooms2) == false);

    return 0;
}```
````


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dongzeli95s-organization.gitbook.io/swe-interview-handbook/algorithm/dfs/keys_and_rooms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.