How to solve Problem - Cyber Attack (Greedy)?

#1

How to solve Problem - Cyber Attack (Greedy)?
Link

#2

This question can be solved greedily by finding Maximum Spanning Tree, MST(which can be found using minimum spanning tree algorithms). For the graph to remain connected, leave the edges of the MST. Now sort the remaining edges in the increasing order of their cost, remove the edges until the sum of costs of removed edges doesn’t exceed the allowed total cost.

Solution - https://ide.codingblocks.com/#/s/29995

1 Like