PROBLEM LINK:
Author: tseccodell
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Graphs,connected components, dfs,
bfs
PROBLEM:
Find minimum number of Zakos to be paid such that their sum is minimum. Find all those Zakos with maximum friends.
QUICK EXPLANATION:
Run DFS/BFS multiple times to find the minimum sum in every connected component.
EXPLANATION:
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.