841. 钥匙和房间

Problem: 841. 钥匙和房间

思路

一个经典的深度优先搜索算法,递归房间中的钥匙,如果递归结束,数量等于全部的房间数量,那么就是可以打开所有房间的门。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    int cnt = 0;
    void dfs(vector<vector<int>>& rooms,vector<bool>& visted,int i) {
        if(visted[i]) return;
        visted[i] = true;
        cnt++;
        if(cnt == rooms.size()) return;
        for (int nextDoor : rooms[i]) {
            if (visted[nextDoor]) continue;// 访问过了
            dfs(rooms, visted,nextDoor);
        }
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visted(rooms.size(),false);
        dfs(rooms,visted,0);
        return cnt == rooms.size();
    }
};