Chương trình kiểm tra có thể mở khóa tất cả các phòng không bằng Python

Cho danh sách rooms, rooms[i] chứa chìa khóa các phòng khác. Phòng 0 mở sẵn. Kiểm tra có thể mở hết tất cả phòng không.

Ví dụ: [[2,0],[3],[1],[]] → True.

Giải thuật

• DFS/BFS từ phòng 0: dùng stack ready, tập seen.
• Lấy phòng từ ready, thêm chìa khóa chưa thấy vào ready.
• Kết thúc: nếu len(seen) == n → True.

Ví dụ minh họa

class Solution:
    def solve(self, rooms):
        n = len(rooms)
        ready = [0]
        seen = set()
        while ready:
            u = ready.pop()
            seen.add(u)
            for v in rooms[u]:
                if v not in seen:
                    ready.append(v)
        return len(seen) == n

ob = Solution()
rooms = [[2,0],[3],[1],[]]
print(ob.solve(rooms))

Đầu vào

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

Đầu ra

True