### 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.