#!/usr/bin/env python
# coding=utf-8
'''
Author: John
Email: johnjim0816@gmail.com
Date: 2020-08-31 16:48:01
LastEditor: John
LastEditTime: 2020-08-31 16:48:39
Discription: 
Environment: 
'''
# Source : https://leetcode.com/problems/keys-and-rooms/
# Author : JohnJim0816
# Date   : 2020-08-31

##################################################################################################### 
#
# There are N rooms and you start in room 0.  Each room has a distinct number in 0, 1, 2, ..., N-1, 
# and each room may have some keys to access the next room. 
# 
# Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, 
# ..., N-1] where N = rooms.length.  A key rooms[i][j] = v opens the room with number v.
# 
# Initially, all the rooms start locked (except for room 0). 
# 
# You can walk back and forth between rooms freely.
# 
# Return true if and only if you can enter every room.
# 
# Example 1:
# 
# Input: [[1],[2],[3],[]]
# Output: true
# Explanation:  
# We start in room 0, and pick up key 1.
# We then go to room 1, and pick up key 2.
# We then go to room 2, and pick up key 3.
# We then go to room 3.  Since we were able to go to every room, we return true.
# 
# Example 2:
# 
# Input: [[1,3],[3,0,1],[2],[0]]
# Output: false
# Explanation: We can't enter the room with number 2.
# 
# Note:
# 
# 	1 <= rooms.length <= 1000
# 	0 <= rooms[i].length <= 1000
# 	The number of keys in all rooms combined is at most 3000.
# 
#####################################################################################################

class Solution:
    ''' 跟孤岛问题类似
    '''
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        st = set() # 保存已走过的房间

        def dfs(n: int) -> None:
            if n in st:
                return 
            st.add(n)
            for i in rooms[n]:
                dfs(i)

        dfs(0)
        return len(rooms) == len(st)
