aboutsummaryrefslogtreecommitdiff
path: root/keys_and_rooms.cpp
blob: d807c7c73575403eb54802a2af91ce4d6ca6011a (plain)
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
26
27
28
29
30
31
32
#include "leetcode.h"

class Solution {
public:
  bool canVisitAllRooms(vvd(int) & rooms) {
    stack<int> dfs;
    dfs.push(0);
    unordered_set<int> seen = {0};
    while (!dfs.empty()) {
      int i = dfs.top();
      dfs.pop();
      for (int j : rooms[i]) {
        if (seen.count(j) == 0) {
          dfs.push(j);
          seen.insert(j);
          if (rooms.size() == seen.size())
            return true;
        }
      }
    }
    return rooms.size() == seen.size();
  }
};

int main() {
  Solution obj;
  vvd(int) rooms = {{1}, {2}, {3}, {}};
  if (obj.canVisitAllRooms(rooms))
    cout << "true";
  else
    cout << "false";
}