Passes to Every Hall

Medium

A museum has n halls numbered 0 to n - 1. Only hall 0 is open; every other hall is locked, and you can enter a hall only if you hold a pass with its number. Each hall contains passes: halls[i] lists the halls whose passes you find in hall i. You keep every pass you pick up and may walk between opened halls as much as you like. Return True if, starting from hall 0, you can get into every hall, and False otherwise.

Example 1

halls=[[2], [], [3, 1], []] → True

Hall 0 holds a pass to hall 2, and hall 2 holds passes to halls 3 and 1. All four halls open.

Example 2

halls=[[1], [0], [3], [2]] → False

Halls 0 and 1 only open each other. The passes to halls 2 and 3 lie inside those halls, so they stay locked.

Constraints

2 ≤ n = len(halls) ≤ 1000
0 ≤ len(halls[i]) ≤ 1000
1 ≤ total number of passes ≤ 3000
0 ≤ halls[i][j] < n
The numbers within one halls[i] are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Do the Links Form a Tree Medium Best Roots for a Tree Medium Isolated Groups in a Network Medium

Input

halls=[[2], [], [3, 1], []]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 86 tests on the server, hidden ones included.