Sponsored
Sponsored
The idea is to use Depth-First Search (DFS) to explore all reachable rooms starting from room 0. This can be implemented either recursively or iteratively with a stack. We maintain a set of visited rooms and attempt to visit all rooms that we have keys for, recursively adding rooms to the visited set as we access them. The process continues until no new rooms can be explored.
1#include <vector>
2#include <unordered_set>
3using namespace std;
4
5class Solution {
6public:
7 bool canVisitAllRooms(vector<vector<int>>& rooms) {
8 unordered_set<int> visited;
9 dfs(rooms, visited, 0);
10 return visited.size() == rooms.size();
11 }
12
13private:
14 void dfs(const vector<vector<int>>& rooms, unordered_set<int>& visited, int room) {
15 if (visited.find(room) == visited.end()) {
16 visited.insert(room);
17 for (int key : rooms[room]) {
18 dfs(rooms, visited, key);
19 }
20 }
21 }
22};In the C++ solution, an unordered_set is used to keep track of visited rooms, and a private DFS method recursively explores accessible rooms. The method inserts each newly visited room to the set and checks all the keys in a room to visit further rooms recursively.
Instead of using DFS, we can also use Breadth-First Search (BFS) to explore the rooms iteratively. We use a queue to maintain the rooms to be visited next. Initially, room 0 is added to the queue. As we visit each room, we add all the keys found in that room to the queue, provided we haven't visited the corresponding rooms yet. This approach ensures a layer-wise exploration similar to BFS.
public class Solution {
public bool CanVisitAllRooms(IList<IList<int>> rooms) {
var visited = new HashSet<int>();
var queue = new Queue<int>();
queue.Enqueue(0);
visited.Add(0);
while (queue.Count > 0) {
int room = queue.Dequeue();
foreach (var key in rooms[room]) {
if (!visited.Contains(key)) {
visited.Add(key);
queue.Enqueue(key);
}
}
}
return visited.Count == rooms.Count;
}
}The C# implementation utilizes a queue and a HashSet for the BFS traversal. Starting with room 0 enqueued, each iteration processes a room by marking it as visited and adding unvisited rooms found through its keys into the queue. Upon completion, the set is checked to determine that all rooms are visited.