Minimum Vertex Cover on Tree
HardTreeDynamic ProgrammingDFSGraph
Description
Given a tree with n nodes (0..n-1) and n-1 edges, return the size of a minimum vertex cover (a smallest set of nodes such that every edge has at least one endpoint in the set).
Examples
Input:
n = 1, edges = []Output:
0Explanation:
A tree with no edges has minimum vertex cover size 0.
Input:
n = 2, edges = [[0,1]]Output:
1Explanation:
A single edge has a minimum vertex cover of size 1; either endpoint suffices.
Input:
n = 5, edges = [[0,1],[0,2],[1,3],[1,4]]Output:
2Explanation:
The set {0, 1} covers every edge of the tree, giving a minimum vertex cover of size 2.
Constraints
- •
1 ≤ n ≤ 1000