题目

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。钥匙 rooms[i][j] = v 可以打开编号为v 的房间。

最初，除0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

输入: [[1],[2],[3],[]]
输出: true
解释:  
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

1
2
3

输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

提示：

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过 3000。

题解

这道题仿佛是酒店老板的开房阴谋。想要开所有房间，我给他规划了两个方法。分别叫BFS和DFS。

BFS

BFS，即广度优先搜索。

老板就问了：“我就是想开房，你能不能讲人话？”
说人话就是，我们按照这个步骤来做——

思路

首先找到0号房间，把所有０号房间的钥匙都开一遍。
进入刚刚开过的房间，再把它们房间里的钥匙再开一遍。
重复以往，层层递进，直到找不到符合要求的节点。

思路很好理解对吧，就是一个从0号房间向外一层层扩散的过程。可是怎么实现呢？

实现

这里就要介绍一下队列，因为广度优先搜索和队列是好基友。
什么是队列？就是一个先进先出的数组，和我们日常生活中的排队很像。当我们向队列插入一个新数的时候，它插在最后，当我们取出一个数的时候，要从头取。就像顾客开房，都是要排队的（假设没有VIP，不许杠！）。

补充——关于在Python中使用队列
在 Python 中，可以使用以下几种方法实现队列

collections包里的deque，对应操作

pop()从尾取出

appendleft() 从头插入

queue包中的queue，对应操作

put() 插入

get() 取出

直接使用list，只要保证只使用

pop() 取出

insert(0,) 插入
或者只使用

append() 插入

list[0]并且del list[0] 取出
两者使用list方法的不同就区别于你把哪个当头，哪个当尾

三种方法各有优劣。

第一种是正统的Python的双端队列，缺点是调用的函数有点复杂，可能一不小心写了append，就不对了。

第二种使用封装的函数很直接，put()和get()不容易搞混淆。但是queue类型其实里面本身就装了一个deque，有点脱裤子放X的感觉。

第三种优势在于不用调包，但是函数使用逻辑可能造成混淆。在
这里，完整版代码采用第二种，好理解，精简版代码采用第三种，省行数。三种方式可以按照你的喜好互相替换，完全不影响结果。

这时候老板又问了：“为什么广度优先搜索和队列能勾搭到一块儿？这和排队有啥关系？”

我们可以这样利用队列实现广度优先搜索。

我们设置一个队列，先把初始房间添加进去
规定每次从队列取出一个房间
把这个房间的所有钥匙放到队列中。
当这个队列为空的时候，说明遍历完成

进队列进去的是钥匙，出来的是房间，其实都是一回事，相当于出来的时候就开锁了。

因为队列每次取出的是最后的，而每次添加的是放在最前面，所以可以想象到，每次先处理的都是层级最少的，最接近初始点的，然后慢慢扩大，这样就实现了广度优先搜索。

老板很好奇：“这个层级顺序有那么重要吗？咱也就是进去看看。”

在这道题目里，层级是不重要的，这也是为什么后来还有个深度优先搜索，也可以解决这道题目。但是广度优先搜索的特点就在于这个层级，在很多题目当中它是很重要的。有时候，对队列取出元素的时候，要设置循环，固定住当前的队列项，对当前的队列项操作——因为当前的队列项一定是相同层级的。例如，在我们寻找到达某个节点的最小步数的时候，层级也就是步数就显得尤为重要了。在leetcode当中，有很多题都是需要广度优先搜索的，这是一种解题的思想，要熟练掌握。而实现这个思想，又离不开队列。两者相辅相成。

老板“啪”地一下打我一拳：“净整这些有的没的，给我写！不然顾客都进来了！”

代码

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited, queue = {0}, [0]
        while queue:
            room_index = queue.pop()
            for key in rooms[room_index]:
                if key not in visited:
                    visited.add(key)
                    queue.insert(0,key)
        return len(visited) == len(rooms)

DFS

DFS，即深度优先搜索。

老板抢着说：“从你这小兔崽子的BFS里，我好想猜到了DFS是什么了，它是不是——”

思路

先找第０个房间的第一个钥匙
进入那个房间，再找它的第一个钥匙
重复以往，直到没钥匙了，那么退回刚刚的房间
找刚刚房间的第二把钥匙
重复以往

思路很好理解对吧，就是一个从中间向一个房间深入的过程。可是怎么实现呢？

实现

还记得标题写的两个方法，三种实现吗？
这是因为 DFS 通常有两种实现方法，一种是递归，另一种是使用栈。
这里就要介绍一下栈，因为深度优先搜索和栈是好基友。
什么是栈？就是一个后进先出的数组，和我们日常生活中的插队很像。当我们向栈插入一个新数的时候，它插在最前面，当我们取出一个数的时候，要从头取。就像老板插队去开房，他不排队，直接插到第一个位置，下一个服务的就是他。

补充——关于在Python中使用栈
直接使用list即可，只使用它的这两个方法

pop()

append()

这时候老板又问了：“为什么广度优先搜索和堆栈能勾搭到一块儿？东扯西扯的家伙。”

我们可以这样利用堆栈实现深度优先搜索。

我们设置一个栈，先把第一个房间添加进去
规定每次从栈中取出一个钥匙
找这个钥匙开的房间，并且把这个房间放到栈中。
当这个栈为空的时候，说明遍历完成

因为栈每次取出的是最后的，而每次添加的也在最后，所以可以想象到，每次先处理的都是最深的，然后慢慢扩大，这样就实现了深度优先搜索。

这时候老板很好奇：“这个深度顺序有那么重要吗？咱就是进去看看。”

在这道题目里，层级是不重要的，这也是为什么前面还有个广度优先搜索，也可以解决这道题目。在leetcode当中，有很多题都是需要深度优先搜索的，这是一种解题的思想，要熟练掌握。而实现这个思想，又离不开栈，递归。两者相辅相成。

老板“啪”地一下打我一拳：“净整这些有的没的，给我写！不然顾客都进来了！”

代码一：使用栈

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited, stack = {0}, [0]
        while stack:
            room_index = stack.pop()
            for key in rooms[room_index]:
                if key not in visited: 
                    visited.add(key)
                    stack.append(key)
        return len(visited) == len(rooms)

代码二：使用递归

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