Keys And Rooms

841. 钥匙和房间

分析

转化为图的遍历问题：
- 将每个房间看作一个节点，钥匙之间的关系看作图的边
- 我们需要从节点 0 开始，遍历整个图，检查是否能够访问所有的节点
深度优先搜索（DFS）：
- 使用递归的方式遍历图，从起点 0 开始访问
- 每访问一个节点（房间），将其标记为已访问
- 对于当前房间中的钥匙（指向其他房间的边），检查对应的房间是否已访问，未访问则递归继续
检查结果：
- 遍历完成后，检查是否所有房间都被访问过。如果有任何房间未被访问，则返回 false；否则返回 true

时间复杂度

每个房间和每把钥匙都会被访问一次，因此时间复杂度为 O(n + m)，其中 n 是房间的数量，m 是所有钥匙的总数量

空间复杂度

图的存储需要 O(n + m) 的空间
访问标记数组占用 O(n) 的空间
递归栈的最大深度为 O(n)

总空间复杂度为 O(n + m)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution
{
public:
    void dfs(int room, std::vector<std::vector<int>>& rooms, std::vector<bool>& visited)
    {
      visited[room] = true;        // 标记房间 room 已访问
      for (int x : rooms[room])    // 遍历房间 room 中的钥匙
        if (!visited[x])           // 如果钥匙指向的房间尚未访问
          dfs(x, rooms, visited);  // 递归访问该房间
    }

    bool canVisitAllRooms(vector<vector<int>>& rooms)
    {
      int n = rooms.size();                 // 房间数量
      std::vector<bool> visited(n, false);  // 初始化访问标记数组
      dfs(0, rooms, visited);               // 从房间 0 开始进行深度优先搜索

      // 检查是否所有房间都被访问
      for (int i = 0; i < n; ++ i)
        if (!visited[i])  // 如果有房间未访问，返回 false
          return false;

      return true;  // 所有房间都被访问，返回 true
    }
};