Skip to content

841. Keys and Rooms 👍

  • Time: $O(|V| + |E|)$
  • Space: $O(|V|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  bool canVisitAllRooms(vector<vector<int>>& rooms) {
    vector<bool> seen(rooms.size());
    dfs(rooms, 0, seen);
    return ranges::all_of(seen, [](int s) { return s == true; });
  }

 private:
  void dfs(const vector<vector<int>>& rooms, int node, vector<bool>& seen) {
    seen[node] = true;
    for (const int child : rooms[node])
      if (!seen[child])
        dfs(rooms, child, seen);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public boolean canVisitAllRooms(List<List<Integer>> rooms) {
    int[] seen = new int[rooms.size()];
    dfs(rooms, 0, seen);
    return Arrays.stream(seen).allMatch(a -> a == 1);
  }

  private void dfs(List<List<Integer>> rooms, int node, int[] seen) {
    seen[node] = 1;
    for (final int child : rooms.get(node))
      if (seen[child] == 0)
        dfs(rooms, child, seen);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
    seen = [False] * len(rooms)

    def dfs(node: int) -> None:
      seen[node] = True
      for child in rooms[node]:
        if not seen[child]:
          dfs(child)

    dfs(0)
    return all(seen)