题目相关
- 原题链接：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);
}
}
}
};
