Hackwithinfy round2 problem.

Revision en1, by en-passant, 2020-06-10 14:23:17

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:

  1. Sorting the vertex on the basis of number of adjacent nodes.

  2. Picking each vertex one by one and running the dfs to collect exactly (k-1) vertex and marking them visited.

  3. 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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English en-passant 2020-06-10 14:23:17 807 Initial revision (published)