mediumGraphsPure DSA~20 min
Can Every Room Be Unlocked From Room Zero
Each room holds keys to other rooms. Starting in room 0 (unlocked), decide whether you can collect keys to open and visit every room.
Problem
There are n rooms labelled 0..n-1, all locked except room 0. rooms[i] is the list of keys (room numbers) found in room i. Starting in room 0, return true if you can visit every room, else false.
Input
A list rooms where rooms[i] holds the keys available in room i.
Output
A boolean: whether all rooms are reachable.
Constraints
- 2 <= n <= 1000
- 0 <= total keys <= 3000
- Keys are room indices, possibly with duplicates.
Examples
Example 1
Input
rooms = [[1],[2],[3],[]]
Output
true
0 -> 1 -> 2 -> 3 visits every room.
Example 2
Input
rooms = [[1,3],[3,0,1],[2],[0]]
Output
false
Room 2 holds the only key to itself, so it is never reachable.