'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List



class Solution:
    # O(N+E), N as number of rooms, E as number of keys
    # O(N) for stack
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        seen = [0] * len(rooms)
        seen[0] = 1
        stack = [0]
        #At the beginning, we have a todo list "stack" of keys to use.
        #'seen' represents at some point we have entered this room.
        while stack:
            node = stack.pop() # get the next key 'node'
            for nei in rooms[node]: # For every key in room # 'node'...
                if not seen[nei]: # ... that hasn't been used yet
                    seen[nei] = 1
                    stack.append(nei) # add the key to the todo list
        return all(seen)
    
    
    def canVisitAllRooms1(self, rooms):
        dfs = [0]
        seen = set(dfs)
        while dfs:
            i = dfs.pop()
            for j in rooms[i]:
                if j not in seen:
                    dfs.append(j)
                    seen.add(j)
                    if len(seen) == len(rooms): return True
        return len(seen) == len(rooms)