leetcode841. 钥匙和房间（中等）

搜索的模板题
思路一：dfs

class Solution {
    
public: 
    int flag[1005] = {
    0};
    int dfs(vector<vector<int>>& rooms, int idx) {
    
        int cnt = 1;
        flag[idx] = 1;
        for (int i = 0; i < rooms[idx].size(); ++i) {
    
            if (!flag[rooms[idx][i]]) cnt += dfs(rooms,rooms[idx][i]);
        }
        return cnt;
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
    
 
        return dfs(rooms, 0) == rooms.size();
    }
};

思路二：bfs

class Solution {
    
public:
    int flag[1005] = {
    0};
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
    

        queue<int> q;
        q.push(0);
        flag[0] = 1;
        int cnt = 0;
        while (!q.empty()) {
    
            int frt = q.front();
            q.pop();
            cnt++;
            for (int i = 0; i < rooms[frt].size(); ++i) {
    
                if (!flag[rooms[frt][i]]) {
    
                    q.push(rooms[frt][i]);
                    flag[rooms[frt][i]] = 1;
                }
            }
        }
        return cnt == rooms.size();
    }
};