A data centre has n servers joined by two-way cables. links[i] lists the servers cabled to server
i. Cables are two-way, so j is in links[i] exactly when i is in links[j], and the
network is connected. An inspector may start at any
server and moves one cable at a time; servers and cables may be used any number of times.
Return the fewest cable moves needed for the inspector to have stood on every server at least once.
Examples
Input: links = [[1, 2, 3], [0], [0], [0]]
Output: 4
Explanation: a star. One best route is 1 -> 0 -> 2 -> 0 -> 3.
1
|
2 - 0 - 3
Input: links = [[1], [0, 2], [1, 3], [2]]
Output: 3
Explanation: walk the chain 0 -> 1 -> 2 -> 3.
Input: links = [[]]
Output: 0
Constraints
1 <= n <= 12; the network is connected; no duplicates or self-links.- The number of servers is tiny on purpose: aim for roughly
2**n * (n + E)work.
Goals
- Extend a BFS state with the set of nodes visited so far
- Encode a set of nodes as a bitmask
- Start the search from every node at once