LC841.钥匙和房间

思路1：DFS

此题的关键在于联想转化成图的遍历问题。
等价于图的遍历，rooms[i] 里面放着t1, t2, t3, 表示从i出发，到t1, t2, t3的三条有向边
如果可以遍历所有的节点，就能够去到所有的房间
第一个示例[[1], [2], [3], []]可以转化成以下的图。

代码：

class Solution {
public:
    void dfs(vector<vector<int>>& rooms, vector<bool>& vis, int cur_pos) {
        vis[cur_pos] = true;
        vector<int> nxt_pos = rooms[cur_pos];
        for (int i = 0, n = nxt_pos.size(); i < n; i++) {
            if (!vis[nxt_pos[i]])
                dfs(rooms, vis, nxt_pos[i]);
        } 
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        // 等价于图的遍历，rooms[i] 里面放着 t1, t2, t3, 表示从i出发，到t1, t2, t3的三条有向边
        // 如果可以遍历所有的节点，就能够去到所有的房间
        int n = rooms.size();
        vector<bool> vis(n, false);
        dfs(rooms, vis, 0);
        for (int i = 0; i < n; i++) {
            if (vis[i] == false) {
                return false;
            }
        }
        return true;
    }
};

思路2：BFS

相当于图的BFS

有了联想就不难了

代码2：

class Solution {
public:
  void bfs(vector<vector<int>>& rooms, vector<bool>& vis) {
      queue<int> q;
      q.push(0);
      vis[0] = true;
      while (!q.empty()) {
          for (int i = 0, qn = q.size(); i < qn; i++) {
              int cur_pos = q.front();
              q.pop();
              for (int k = 0, nr = rooms[cur_pos].size(); k < nr; k++) {
                  if (!vis[rooms[cur_pos][k]]) {
                      q.push(rooms[cur_pos][k]);
                      vis[rooms[cur_pos][k]] = true;
                  }
              }
          }
      }
  }
  bool canVisitAllRooms(vector<vector<int>>& rooms) {
      // 等价于图的遍历，rooms[i] 里面放着 t1, t2, t3, 表示从i出发，到t1, t2, t3的三条有向边
      // 如果可以遍历所有的节点，就能够去到所有的房间
      int n = rooms.size();
      vector<bool> vis(n, false);
      bfs(rooms, vis);
      for (int i = 0; i < n; i++) {
          if (vis[i] == false) {
              return false;
          }
      }
      return true;
  }
};