Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Plant Trees, Save Life

By dhruba_1603088 · Limits 1s, 512 MB

There are n students in a school. Some of them are friends with each other. You want to make the school clean. So you have to give ice-cream to each student so he or she starts planting trees.
When one plants a tree, he/she tells it to all of his friends and they start to plant trees and tell their friends too (without any ice creams) and so on.

i-th student wants xi ice creams in exchange for starting the trend.
Your work is finished when all n students start planting trees. What is the minimum number of ice creams you need to distribute to finish the work?


The first line contains two integer numbers n and k — the number of students and the number of pairs of friends.
The second line contains n integer numbers xi (0 <= xi <= 109)

Then there will be k lines. Each will contain a pair of numbers(a,b) where a and b are friends (1 <= a,b <= n) and a is not equal to b.


For 10 points: 1 ≤ n ≤ 700, 0 ≤ k ≤ 300

For 40 points: 1 ≤ n ≤ 105, 0 ≤ k ≤ 1200

For 100 points: 1 ≤ n ≤ 105, 0 ≤ k ≤ 105


Print the minimum amount of ice creams you need to finish the work.


10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10



61% Solution Ratio

nahidhasan98Earliest, Oct '19

coder_8115Fastest, 0.0s

subhashis_cseLightest, 524 kB

lelbabaShortest, 545B


Login to submit


Use DSU to calculate the sum of minimum values in every connected component.