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.

Difficulty: interview

Starter code:

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        

Solutions:
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(node, visited):
            if node in visited:
                return
            visited.add(node)
            for nei in rooms[node]:
                if nei in visited:
                    continue
                dfs(nei,visited)
            return
        visited = set()
        dfs(0, visited)
        if len(visited) == len(rooms):
            return True
        else: 
            return False
            


from collections import deque 

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        seen = [False for i in range(len(rooms))]
        seen[0] = True 
        stack = deque()
        stack.append(0)
        
        while stack:
            room = stack.pop()
            for key in rooms[room]:
                if not seen[key]:
                    seen[key] = True 
                    stack.append(key)
        
        return all(seen)

                
                
        


class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def recur(room, visited):
            if room in visited: return False
            visited.append(room)
            if len(visited) == len(rooms): return True
            for i in rooms[room]:
                if recur(i, visited): return True
            return False

        return recur(0, [])

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        list_of_rooms_visited = [0]
        
        def check(arr):
            #print(list_of_rooms_visited)
            for j in arr:
                if j not in list_of_rooms_visited:
                    list_of_rooms_visited.append(j)
                    check(rooms[j])
            return
                
        check(rooms[0])
        if len(list_of_rooms_visited)!=len(rooms):
            return False
        else:
            return True


class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        self.visited = [0]
        
        self.dfs(rooms, 0)
        #print(self.visited)
        if len(self.visited) == len(rooms):
            return True
        return False
        
    def dfs(self, rooms, i):
        keys = rooms[i]
        
        for key in keys:
            if key not in self.visited:
                self.visited.append(key)
                self.dfs(rooms, key)
                
            
        return


class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        self.visited = [0]
        
        self.dfs(rooms, 0)
        #print(self.visited)
        if len(self.visited) == len(rooms):
            return True
        return False
        
    def dfs(self, rooms, i):
        keys = rooms[i]
        
        for key in keys:
            if key not in self.visited:
                self.visited.append(key)
                self.dfs(rooms, key)
                
            else:
                continue
        return


class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        self.visited = []
        self.dfs(rooms, 0)
        return len(self.visited) == len(rooms)
    
    def dfs(self, rooms, room_id):
        if room_id in self.visited:
            return
        self.visited.append(room_id)
        for key in rooms[room_id]:
            self.dfs(rooms, key)


class GraphNode:
    def __init__(self):
        self.neighbors = set()
    
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        nodes = [GraphNode() for i in range(len(rooms))]
        for index, keys in enumerate(rooms):
            for key in keys:
                nodes[index].neighbors.add(nodes[key])
        
        stack = [nodes[0]]
        visited = set()
        while stack:
            node = stack.pop()
            if node in visited:
                continue
            visited.add(node)
            for neighbor in node.neighbors:
                stack.append(neighbor)
                
        return len(visited) == len(rooms)

import numpy as np
class Solution(object):
    def canVisitAllRooms(self, rooms):
        seenRooms = np.zeros(len(rooms), dtype = bool)
        Keys = [0]
        while(len(Keys)!=0):
            curr = Keys.pop(0)
            seenRooms[curr] = True
            for key in rooms[curr]:
                if not seenRooms[key]:
                    Keys.append(key)
        return True if all(seenRooms) else False
                
            


import numpy as np
class Solution(object):
    def canVisitAllRooms(self, rooms):
        seenRooms = np.zeros(len(rooms), dtype = bool)
        stackKeys = [0]
        while(len(stackKeys)!=0):
            curr = stackKeys.pop()
            if not seenRooms[curr]:
                seenRooms[curr] = True
                for key in rooms[curr]:
                    stackKeys.append(key)
        return True if all(seenRooms) else False
                
            


class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        
        q=deque([])
        vis=[False]*len(rooms)
        q.append(0)
        
        while q:
            ver=q.popleft()
            vis[ver]=True
            for neigh in rooms[ver]:
                if(vis[neigh]!=True):
                    q.append(neigh)

        if(False in vis):
            return False
        else:
            return True
          
            
        


class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        rooms_to_visit = [i for i in range(n)]
        
        def dfs(curr_room, rooms_left, keys):
            # print(curr_room, rooms[curr_room], rooms_left, keys)
            if len(rooms_left) == 0:
                return True
            else:
                res = False
                if len(keys) == 0:
                    return False
                for key in keys:
                    if key in rooms_left:
                        rooms_left.remove(key)
                        tmp_keys = (keys.union(set(rooms[key]))).intersection(set(rooms_left))
                        return dfs(key, rooms_left, tmp_keys)
                        rooms_left.append(key)
            
        return dfs(0, list(range(1,n)), set(rooms[0]))

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    
        q = deque([0])
        visited = set([0])
        while q:
            r = q.pop()
            for k in rooms[r]:
                if k not in visited:
                    visited.add(k)
                    q.append(k)
                
        return len(visited)==len(rooms)

class Room:
    def __init__(self, num, keys):
        self.num = num
        self.keys = keys
        self.visited = False
        
class Solution:
    def explore(self, room_id, all_rooms):
        cur_room = all_rooms[room_id]
        if cur_room.visited:
            return
        
        cur_room.visited = True
        for key in cur_room.keys:
            self.explore(key, all_rooms)
        
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        all_rooms = [Room(i, keys) for i, keys in enumerate(rooms)]
        self.explore(0, all_rooms)
        
        for room in all_rooms:
            if not room.visited:
                return False
            
        return True

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        seen = [False]*len(rooms)
        seen[0]= True
        stack =[0]
        while stack:
            nodes = stack.pop()
            for node in rooms[nodes]:
                if not seen[node]:
                    seen[node]=True
                    stack.append(node)
        return all(seen)

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        
        graph=defaultdict(list)
        
        for i in range(len(rooms)):
            for j in range(len(rooms[i])):
                graph[i].append(rooms[i][j])
                
        visited=set()
        q=[0]
        
        while q:
            item = q.pop(0)
            if item not in visited:
                visited.add(item)
                for val in graph[item]:
                    q.append(val)
        
        if len(visited)==len(rooms):
            return True
        else:
            return False

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        
        graph=defaultdict(list)
        
        for i in range(len(rooms)):
            for j in range(len(rooms[i])):
                graph[i].append(rooms[i][j])
                
        visited=set()
        item=0
        
        
        def rec(item):
            if item not in visited:
                visited.add(item)
                for val in graph[item]:
                    rec(val)
        rec(item)
        
        if len(visited)==len(rooms):
            return True
        else:
            return False

class Solution:
    def canVisitAllRooms(self, rooms):
        graph = {}
        visited = {}
        for node, edges in enumerate(rooms):
            visited[node] = False
            graph[node] = []
            for edge in edges:
                graph[node].append(edge)
        
        def DFS(visited, graph, node):
            visited[node] = True
            for neighbour_node in graph[node]:
                if not visited[neighbour_node]:
                    DFS(visited, graph, neighbour_node)
        
        islands = 0

        for node in visited:
            if not visited[node]:
                islands += 1
                DFS(visited, graph, node)

        return islands == 1

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        
        def dfs(curRoom, visited):
            visited[curRoom] = True
            
            for key in rooms[curRoom]:
                if not visited[key]:
                    dfs(key, visited)
        
        visited = [False] * len(rooms)
        dfs(0, visited)
        #print(visited)
        return all(visited)

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        rem_rooms = [i for i in range(1, len(rooms))]

        visited = set()
        def dfs(r, key):
            stack = [key]

            while stack and rem_rooms:
                element = stack.pop()
                if element in rem_rooms:
                    rem_rooms.remove(element)

                if element not in visited:
                    visited.add(element)

                    for neighbour in rooms[element]:
                        stack.append(neighbour)

        dfs(rooms, 0)

        return len(rem_rooms) == 0