[LeetCode] 841. Keys and Rooms

タイトルの説明
There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, …, N-1, and each room may have some keys to access the next room.
Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, …, N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.
Initially, all the rooms start locked (except for room 0).
You can walk back and forth between rooms freely.
Return true if and only if you can enter every room.
Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:
1 <= rooms.length <= 1000 0 <= rooms[i].length <= 1000 The number of keys in all rooms combined is at most 3000.
2 D配列が与えられ、配列の各行は現在の部屋から入ることができる部屋のリストを表します.room-0から、すべての部屋に入ることができるかどうかを求めます.本題で与えられた配列は図と考えられ,この問題は図の特定のノードから全図を遍歴できるかどうかの問題に変換される.bfsまたはdfs検索を使用して解決できます.
C++実装
bfsバージョン

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int size = rooms.size();
        vector<bool> visited(size, false);
        visited[0] = true;
        for (const int room : rooms.front())
        {
            bfs(room, rooms, visited);
        }

        for (const bool v : visited)
        {
            if (!v) return false;
        }
        return true;
    }
    void bfs(const int start,
             const vector<vector<int>>& rooms,
             vector<bool>& visited)
    {
        queue<int> que;
        que.push(start);
        while(!que.empty())
        {
            int front = que.front();
            visited[front] = true;
            que.pop();
            for (const int room : rooms[front])
            {
                if (!visited[room])
                {
                    que.push(room);
                }
            }
        }
    }
};

dfsバージョン

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int size = rooms.size();
        vector<bool> visited(size, false);
        visited[0] = true;
        for (const int room : rooms.front())
        {
            dfs(room, rooms, visited);
        }

        for (const bool v : visited)
        {
            if (!v) return false;
        }
        return true;
    }
    void dfs(const int start,
             const vector<vector<int>>& rooms,
             vector<bool>& visited)
    {
        visited[start] = true;
        for (const int room : rooms[start])
        {
            if (!visited[room])
            {
                dfs(room, rooms, visited);
            }
        }
    }
};