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.
1using System.Collections.Generic;
2
3public class Solution {
4 public bool CanVisitAllRooms(IList<IList<int>> rooms) {
5 var visited = new HashSet<int>();
6 DFS(rooms, visited, 0);
7 return visited.Count == rooms.Count;
8 }
9
10 private void DFS(IList<IList<int>> rooms, HashSet<int> visited, int room) {
11 if (!visited.Contains(room)) {
12 visited.Add(room);
13 foreach (var key in rooms[room]) {
14 DFS(rooms, visited, key);
15 }
16 }
17 }
18}In the C# implementation, a HashSet is used to track visited rooms. A recursive DFS function explores rooms starting from room 0. Each key in the current room is used to explore further rooms, and all visited rooms are counted at the end to determine if all rooms can be visited.
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.
1
This C implementation uses an array-based queue for BFS traversal. Mark room 0 as visited and begin processing with BFS, updating the visited status as rooms are dequeued and processed. Any unvisited room found through keys is enqueued. Finally, it ensures all rooms have been visited.