Unlocking Rooms With Keys

medium graph dfs

Problem

Each room contains a list of keys to other rooms. You start in room 0 (initially unlocked); after entering a room you collect every key it contains. Decide whether every room is eventually reachable. DFS or BFS from room 0 across the directed key graph.

Inputrooms = [[1,3],[3,0,1],[2],[0]]

Outputfalse

Room 2 is unreachable — no key for it appears in any room you can enter.

rooms (e.g. "1,3; 3,0,1; 2; 0")

def can_visit_all(rooms):
    seen = [False] * len(rooms)
    stack = [0]; seen[0] = True
    while stack:
        u = stack.pop()
        for v in rooms[u]:
            if not seen[v]:
                seen[v] = True; stack.append(v)
    return all(seen)

function canVisitAll(rooms) {
  const seen = new Array(rooms.length).fill(false);
  const stack = [0]; seen[0] = true;
  while (stack.length) {
    const u = stack.pop();
    for (const v of rooms[u]) if (!seen[v]) { seen[v] = true; stack.push(v); }
  }
  return seen.every(Boolean);
}

class Solution {
    public boolean canVisitAll(List<List<Integer>> rooms) {
        boolean[] seen = new boolean[rooms.size()];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0); seen[0] = true;
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : rooms.get(u)) if (!seen[v]) { seen[v] = true; stack.push(v); }
        }
        for (boolean s : seen) if (!s) return false;
        return true;
    }
}

bool canVisitAll(vector<vector<int>>& rooms) {
    vector<bool> seen(rooms.size(), false);
    stack<int> st;
    st.push(0); seen[0] = true;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        for (int v : rooms[u]) if (!seen[v]) { seen[v] = true; st.push(v); }
    }
    for (bool s : seen) if (!s) return false;
    return true;
}

Time: O(V + E) Space: O(V)