This a question from a recent contest which ended few hours ago.
Problem statement
You are given a tree consisting of N vertices,What is the minimum number of vertices that should be removed such that all the remaining parts of the initial tree contains less than K vertices.
End
Since the verdict was hidden during the contest I am not sure whether my approach is correct. My approach goes as follows:
Sorting the vertex on the basis of number of adjacent nodes.
Picking each vertex one by one and running the dfs to collect exactly (k-1) vertex and marking them visited.
If a path has already less than K vertices ignore it or ,increment the answer.
If it's a common problem please point out as I have just started learning graphs.
Comments (0)
