Find minimum number of Zakos to be paid such that their sum is minimum. Find all those Zakos with maximum friends.
Run DFS/BFS multiple times to find the minimum sum in every connected component.
In this problem you are given an undirected graph with weighted vertices.
Store the pair of weight of the vertex and its position in a vector V. Then create adjacency representation for all edges. Sort the vector V,in non-decreasing order, so that we get vertex with minimum weights.Now for each connected component run DFS and simultaneously add the minimum weight vertex to final answer.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.