[HELP] Komprise Online Assessment Question


I would be grateful if someone can give a direction on where to start with the above question

I was thinking of a greedy approach by placing the guard with maximum number of incoming/outgoing edges but failed on the sample test cases.

Thank you

you can model this problem as a graph problem.
and then sort the node in decreasing order of the number of edges.
and start traversing from the node with the highest number of edges to the lowest no of edges.
put one guard at the node and mark all the connected nodes to this node as visited and so do for the remaining node which are not guarded yet.

if I am thinking wrong please correct me :innocent: