#26HardBit Manipulation & Graph Search· BFS over (Node, Visited-Set) States

Shortest Path Visiting All Nodes

You are given an undirected, connected graph with `n` nodes labelled `0` to `n - 1`, as an adjacency list: `graph[i]` lists the neighbours of node `i`. Return the number of edges in the shortest walk that visits every node at least once. The walk may start and end at any nodes, and it may revisit nodes and reuse edges as often as needed.

Input format

graph: adjacency list, an array of n arrays of neighbour indices

Output format

Integer: the length (number of edges) of the shortest walk covering all nodes

Examples

Input: graph = [[1, 2, 3], [0], [0], [0]]

Output: 4

A star with three leaves: for example 1 -> 0 -> 2 -> 0 -> 3 uses 4 edges.

Input: graph = [[1], [0, 2], [1, 3], [2]]

Output: 3

A path of four nodes is covered by walking it end to end.

Input: graph = [[]]

Output: 0

A single node is already visited, so no edges are needed.

Constraints

1 <= n <= 12
0 <= graph[i].length < n
graph[i] does not contain i, and if j is in graph[i] then i is in graph[j].
The graph is connected.

Study first

Dynamic Programming Patterns

#graphs
#breadth-first-search
#bit-manipulation
#bitmask
#dynamic-programming