841. Keys and Rooms

Solution idea

DFS

• 题目要求只要能从room 0出发到达所有其他rooms就行
  • 不强求从room 0出发，必须遍历所有rooms，最后到达room n-1
• input graph可能有环，所以用 hashmap visited 记录遍历过的节点以避免回到遍历过的节点
  • 同时，visited记录了从room 0可以遍历到的所以rooms, 最后只用检查哪个room不在 visited中就可以决定返回true/false

Time complexity = $O(V+E)$

Resource

代码随想录-841.钥匙和房间