0841. 钥匙和房间 #
- 标签:深度优先搜索、图
- 难度:中等
题目大意 #
描述:有 n
个房间,编号为 0
~ n - 1
,每个房间都有若干把钥匙,每把钥匙上都有一个编号,可以开启对应房间号的门。最初,除了 0
号房间外其他房间的门都是锁着的。
现在给定一个二维数组 rooms
,rooms[i][j]
表示第 i
个房间的第 j
把钥匙所能开启的房间号。
要求:判断是否能开启所有房间的门。如果能开启,则返回 True
。否则返回 False
。
说明:
- $n == rooms.length$。
- $2 \le n \le 1000$。
- $0 \le rooms[i].length \le 1000$。
- $1 \le sum(rooms[i].length) \le 3000$。
- $0 \le rooms[i][j] < n$。
- 所有 $rooms[i]$ 的值互不相同。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:深度优先搜索 #
当 x
号房间有 y
号房间的钥匙时,就可以认为我们可以通过 x
号房间去往 y
号房间。现在把 n
个房间看做是拥有 n
个节点的图,则上述关系可以看做是 x
与 y
点之间有一条有向边。
那么问题就变为了给定一张有向图,从 0
节点开始出发,问是否能到达所有的节点。
我们可以使用深度优先搜索的方式来解决这道题,具体做法如下:
- 使用 set 集合变量
visited
来统计遍历到的节点个数。 - 从
0
节点开始,使用深度优先搜索的方式遍历整个图。 - 将当前节点
x
加入到集合visited
中,遍历当前节点的邻接点。- 如果邻接点不再集合
visited
中,则继续递归遍历。
- 如果邻接点不再集合
- 最后深度优先搜索完毕,判断一下遍历到的节点个数是否等于图的节点个数(即集合
visited
中的元素个数是否等于节点个数)。- 如果等于,则返回
True
- 如果不等于,则返回
False
。
- 如果等于,则返回
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n + m)$,其中 $n$ 是房间的数量,$m$ 是所有房间中的钥匙数量的总数。
- 空间复杂度:$O(n)$,递归调用的栈空间深度不超过 $n$。