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.

Source: leetcode | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

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):
			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)
		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 = []
		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


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):
			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):
		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)
		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