A museum has n rooms numbered 0 .. n-1, and corridors is a list of pairs [a, b], each a
corridor between rooms a and b (no corridor joins a room to itself and no pair appears twice).
A guard posted in a room watches every corridor that starts or ends in that room.
Write fewest_guards(n, corridors) that returns the smallest number of guards needed so that every
corridor is watched.
Every corridor needs a guard at one of its two ends, but there are up to 60 rooms: trying every set of rooms, or simply branching on "which end of this corridor gets the guard", takes far too long on the larger tests.
The larger tests use museum(n, count, seed), available in your code, which returns
(n, corridors) with count random corridors; call it as fewest_guards(*museum(40, 80, 1)).
Examples
Input: n = 5, corridors = [[0, 1], [0, 2], [0, 3], [0, 4]]
Output: 1
Explanation: one guard in room 0 watches all four corridors.
Input: n = 4, corridors = [[0, 1], [1, 2], [2, 3], [3, 0]]
Output: 2
Explanation: guards in rooms 0 and 2 (or 1 and 3). One guard can watch only two corridors.
Input: n = 6, corridors = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 5], [5, 3]]
Output: 4
Explanation: each triangle 0-1-2 and 3-4-5 needs two guards, for example 1, 2, 3, 5.
Constraints
1 <= n <= 60,0 <= len(corridors) <= 2000 <= a, b < n,a != b, no corridor is listed twice
Goals
- Branch on the choice that removes the most of the problem
- Apply forced moves before branching
- Prune with a lower bound that is cheap to compute