Keys and Rooms — DFS/BFS Graph Reachability
Sanjeev SharmaAdvertisement
Problem
There are n rooms; room 0 is unlocked. Each room has a list of keys. Return true if you can visit all rooms.
Approach — DFS reachability
Start from room 0, add discovered keys to stack/queue. Visit newly unlocked rooms. Check if all n rooms visited.
Time: O(V+E) | Space: O(V)
Solutions
Python
class Solution:
def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
visited=set([0]); stack=[0]
while stack:
room=stack.pop()
for key in rooms[room]:
if key not in visited:
visited.add(key); stack.append(key)
return len(visited)==len(rooms)
C++
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms){
int n=rooms.size(); vector<bool> vis(n,false);
stack<int> s; s.push(0); vis[0]=true; int cnt=1;
while(!s.empty()){
int r=s.top();s.pop();
for(int k:rooms[r]) if(!vis[k]){vis[k]=true;s.push(k);cnt++;}
}
return cnt==n;
}
};
Complexity
- Time: O(V+E) | Space: O(V)
Advertisement
