---
tags: leetcode
---

# [841. Keys and Rooms](https://leetcode.com/problems/keys-and-rooms/)
---
# My Solution
## Solution 1: DFS
### The Key Idea for Solving This Coding Question
### C++ Code 1

#define WHITE (1)  // not visited
#define GRAY  (2)  // visiting the node and its descendants
#define BLACK (3)  // have visited this node and all its descendants.

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int cnt = 0, n = rooms.size();
        vector<int> state(n, WHITE);
        
        dfs(rooms, state, 0, cnt);
        return cnt == n;
    }
    
private:
    void dfs(vector<vector<int>> &rooms, vector<int> &state, int currRoom, int &cnt) {
        state[currRoom] = GRAY;
        ++cnt;
        
        for (int i = 0; i < rooms[currRoom].size(); ++i) {
            if (state[rooms[currRoom][i]] != WHITE) {
                continue;
            }
            dfs(rooms, state, rooms[currRoom][i], cnt);
        }
        
        state[currRoom] = BLACK;
    }
};

#### Time Complexity
$O(n)$
* $n$ is the lenght of `rooms`.
#### Space Complexity
$O(H)$
* $H$ is the height while we traverse the graph described by `rooms`.
* In the worst case, the space complexity is $O(n)$.

### C++ Code 2

#define WHITE (1)
#define GRAY  (2)
#define BLACK (3)

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size(), cnt = 0;
        vector<int> state(n, WHITE);
        
        for (int i = 0; i < n; ++i) {
            if (state[i] == WHITE) {
                dfs(rooms, state, i);
                ++cnt;
            }
        }
        
        return cnt == 1;
    }
    
private:
    void dfs(vector<vector<int>> &rooms, vector<int> &state, int currRoom) {
        state[currRoom] = GRAY;
        
        vector<int> &nextRooms = rooms[currRoom];
        int n = nextRooms.size();
        for (int i = 0; i < n; ++i) {
            if (state[nextRooms[i]] != WHITE) {
                continue;
            }
            dfs(rooms, state, nextRooms[i]);
        }
        
        state[currRoom] = BLACK;
    }
};

#### Time Complexity
$O(n)$
* $n$ is the lenght of `rooms`.
#### Space Complexity
$O(H)$
* $H$ is the height while we traverse the graph described by `rooms`.
* In the worst case, the space complexity is $O(n)$.

## Solution 2: BFS
### The Key Idea for Solving This Coding Question
### C++ Code

#define WHITE (1)  // not visited
#define GRAY  (2)  // visiting the node and its descendants
#define BLACK (3)  // have visited this node and all its descendants.

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int cnt = 1, n = rooms.size();
        vector<int> state(n, WHITE);
        queue<int> q;
        
        q.push(0);
        state[0] = GRAY;
        while (!q.empty()) {
            int currRoom = q.front();
            q.pop();
            
            for (int i = 0; i < rooms[currRoom].size(); ++i) {
                if (state[rooms[currRoom][i]] != WHITE) {
                    continue;
                }
                q.push(rooms[currRoom][i]);
                state[rooms[currRoom][i]] = GRAY;
                ++cnt;
            }
            state[currRoom] = BLACK;
        }
        
        return cnt == n;
    }
};

### Time Complexity
$O(n)$
* $n$ is the lenght of `rooms`.
### Space Complexity
$O(n)$
# Miscellane
<!--
# Test Cases

[[1],[2],[3],[]]

[[1,3],[3,0,1],[2],[0]]

[[4],[3],[],[2,5,7],[1],[],[8,9],[],[],[6]]

-->