Given an undirected connected graph, return the minimum number of edges in a path that visits every node at least once. Pattern focus: Bitmask DP. Track the current node together with the set of visited nodes.
graph = adjacency list of an undirected graph
minimum number of edges needed to visit every node
Example 1:
Input:
graph = [[1,2],[0,2],[0,1]]
Output:
2
Explanation:
A triangle can be covered in 2 edges by visiting all three nodes.
Example 2:
Input:
graph = [[1,2,3],[0],[0],[0]]
Output:
4
Explanation:
A star graph requires revisiting the center to reach every leaf.
Example 3:
Input:
graph = [[1],[0,2],[1,3],[2]]
Output:
3
Explanation:
A path graph can be traversed once from one end to the other.