思考:
DFS的基本題
檢查連通性用DFS
1.進入第零號房間後可以看到有哪些房間的鑰匙
2.用DSF掃描每一個房間有哪些鑰匙可以去
3.用額外vector紀錄那些房間是可以進入的

class Solution {
public:
    void dfs(int i, vector<vector<int>>& rooms, vector<int>& visit){
        // i 是 第n間房間
        visit[i] = true;
        //掃描這個房間內有誰的鑰匙
        for(int key : rooms[i]){
            //如果有這把鑰匙但沒去過就DSF他
            if(visit[key] == false){
                dfs(key, rooms, visit);
            }
        }
    }


    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector <int> visit (rooms.size(), false);
        //進入第零間room
        dfs(0, rooms, visit);
        for(int i = 0; i < visit.size(); i++){
            if(visit[i] == false){
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    void dsf(int i, vector<vector<int>>& rooms, vector<bool>& v){
        //已進入 i 號房
        v[i] = true;
        //掃描這個i號房有甚麼鑰匙
        for(int key : rooms[i]){
            if(v[key] == false){
                //代表有key號房的鑰匙但沒去過 所以去拜訪
                dsf(key, rooms, v);
            }
        }
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector <bool> v(rooms.size(), 0);
        dsf(0, rooms, v);
        for(bool i : v){
            if(i == false){
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    void DFS(vector<vector<int>>& rooms, vector <bool>& vis, int start){
        vis[start] = true;
        for(auto i : rooms[start]){
            if(i != NULL && vis[i] == false){
                DFS(rooms, vis, i);
            }
        }
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        vector <bool> vis(n, false);
        DFS(rooms, vis, 0);
        
        for(auto i : vis){
            if(i == false){
                return false;
            }
        }
        return true;



    }
};