< Back to forum

### E - Destruction

Problem Statement

Asked by: Anonymous on Sept. 24, 2021, 4:05 p.m. Last updated on Sept. 24, 2021, 4:05 p.m.

Preview

##### Enter your comment details below:

Preview

The problem is based on the concept of minimum spanning tree and specifically on Kruskal's algorithm.

The key point to notice here is that after removal of edges, the total cost of edges in the remaining tree is minimum possible. That gives us and idea of the concept of minimum spanning tree.
So, we can sort the edge weights in ascending order and use Kruskal's algorithm to complete the tree. The only edge case here is that there are negative weights also, so you should pick negative weights as well even if they are not a part of the minimum spanning tree.

mahawarvishal10 last updated on Sept. 24, 2021, 10:54 p.m.

##### Instruction to write good question
1. 1. Write a title that summarizes the specific problem
2. 2. Pretend you're talking to a busy colleague
3. 3. Spelling, grammar and punctuation are important!