『图』钥匙和房间841

题目相关

• 原题链接：841. 钥匙和房间 - 力扣（LeetCode）
• 涉及知识：图、深度优先遍历、广度优先遍历
• 题目难度：★

题目解读

由题意知，各房间与其内其他房间的钥匙构成了有向图的结点和边，我们需要做的是判断是否存在所有某点通往其他结点的路径。

C++相关

如果是DFS，我们可以通过编写递归函数来实现；如果是BFS，我们可以考虑集合+队列来实现。

具体实现

BFS：

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        set<int> visited; //已访问房间集合
        queue<int> tmp; //待访问房间队列
        tmp.push(0);
        visited.insert(0);
        while (!tmp.empty()) {
            int i = tmp.front();
            tmp.pop();
            for (int j : rooms[i]) {
                if (!visited.count(j)) { //j号房间未被访问
                    visited.insert(j);
                    tmp.push(j);
                }
            }
        }
        return visited.size() == rooms.size();
    }
};

DFS:

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        set<int> visited; //已访问房间集合
        BFS(rooms, visited, 0);
        return visited.size() == rooms.size();
    }
    void DFS(vector<vector<int>>& rooms, set<int>& visited, int num) {
        visited.insert(num);
        for (int i: rooms[num]) {
            if (!visited.count(i)) {
                BFS(rooms, visited, i);
            }
        }
    }
};