Tour Every Room
A house has len(doors) rooms numbered from 0. doors[i] lists the rooms that share a door with room i; the lists are symmetric, no room has a door to itself and no door is listed twice.
You may begin in any room, end in any room, and pass through rooms and doors as often as you like. Return the smallest number of door passes in a walk that visits every room at least once. If some room cannot be reached from another, return -1. A house with one room needs 0 passes.
Example 1
doors [[1,2],[0,3],[0,3],[1,2]]
returns 3
The rooms form a square; walking 0, 1, 3, 2 passes 3 doors and sees every room.
Example 2
doors [[1],[0],[]]
returns -1
Room 2 has no door, so it can never be visited from the others.
Constraints
1 <= len(doors) <= 100 <= doors[i][j] < len(doors)anddoors[i][j] != i- The lists are symmetric and no door is repeated
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Turn the SignpostsHard
- Use Every TicketHard
- Arrows In and OutBeginner
- Build the Neighbor ListsBeginner
- Can You Walk ItBeginner
- Count the LinksBeginner
- Dead EndsBeginner
- Degree of Every NodeBeginner