一、题目
提示：
n == rooms.length2 <= n <= 10000 <= rooms[i].length <= 10001 <= sum(rooms[i].length) <= 30000 <= rooms[i][j] < n所有 rooms[i] 的值 互不相同二、思路
dfs基础题。以测试用例2为栗子画了个图：
像右边，3号为父结点和孩子结点之间是不连接的，因为0号房间已经遍历过了。
一开始用版本一的代码有些测试用例没过，找了好久是因为dfs的递归边界和访问时的操作出了问题，不应该简单用??cur_num???（当前已经访问过的房间种数）进行判断是否完成任务，想法上没问题，但是我设置的??cur_num???是全局变量，遍历多条路径时都会依次累加这个??cur_num???值就不对啦，所以可以直接判断哈希表??visited???的size是否为房间总数即可—>作为最后成功与否的判断；并且也不用??cur_num??了。
当然从时间复杂度的结果看，还可进一步剪枝。
三、代码
版本一：错误代码（只过了48个测试用例）：
class Solution {private: unordered_map<int, int> visited; //已经访问过的房间个数 int cur_num = 0; int room_num;public: bool canVisitAllRooms(vector<vector<int>>& rooms) { if(rooms.size() == 0){ return false; } int room_num = rooms.size(); dfs(rooms, 0, cur_num); if(room_num == cur_num){ return true; }else{ return false; } } //cur_num为当前已经访问过的房间个数（种类） void dfs(vector<vector<int>>& rooms, int room_id, int cur_num){ //递归边界判断 if(visited[room_id] || cur_num == room_num){ return; } //先访问当前的房间 //vector<int>id = rooms[room_id]; visited[room_id] = 1; cur_num++; //遍历当前房间拥有的钥匙的房间 for(auto& next_i: rooms[room_id]){ dfs(rooms, next_i, cur_num); } }};
版本二：正确代码：
class Solution {private: unordered_map<int, int> visited; //已经访问过的房间个数 int room_num;public: bool canVisitAllRooms(vector<vector<int>>& rooms) { if(rooms.size() == 0){ return false; } int room_num = rooms.size(); dfs(rooms, 0); if(room_num == visited.size()){ return true; }else{ return false; } } //cur_num为当前已经访问过的房间个数（种类） void dfs(vector<vector<int>>& rooms, int room_id){ //递归边界判断 if(visited[room_id]){ return; } //先访问当前的房间 //vector<int>id = rooms[room_id]; visited[room_id] = 1; //遍历当前房间拥有的钥匙的房间 for(auto& next_i: rooms[room_id]){ dfs(rooms, next_i); } }};
像一颗深绿色的宝石镶嵌在云南大地上，
