Learn
Exam

Building a synchronized server

Difficulty
INTERMEDIATE

Problem

Kim Node is the CEO of the global company "Gugle."
"Gugle" owns a total of n servers that must all be synchronized. However, not all servers are directly connected, and information about synchronizable server pairs is provided as syncs.

Write a function solution that calculates and returns the minimum cost required for Kim Node to synchronize all servers.

For example, the server connection status of "Gugle" is as follows:

There are 6 servers, and 7 pairs of servers can be synchronized, represented as edges. The cost of synchronizing each pair is shown on the corresponding edge.

By synchronizing the servers as shown in the image, the minimum cost is 32.

Constraints

  • n is the number of servers, where 1≤n≤20,0001 \leq n \leq 20,000.
  • syncs contains synchronization information, where each element is an array [x, y, w]:
    • The length of syncs is between 1 and 500,000 inclusive.
    • x and y are natural numbers between 1 and n, representing the two servers to be synchronized.
    • w is a natural number between 1 and 10,000, representing the cost of synchronizing the two servers.

Test Case

Test Case Number n syncs return
1 6 [[2,4,1],[5,3,5],[1,5,10],[4,6,12],[3,2,8],[5,4,9],[3,4,4]] 32
2 5 [[3,2,2],[5,4,6],[5,1,5],[2,4,4]] 17
3 9 [[8,5,9],[6,7,2],[9,5,1],[2,3,10],[7,4,6],[4,9,5],[5,7,7],[6,8,8],[4,5,3],[9,7,7],[9,8,2],[8,7,10],[4,6,7],[6,9,1],[6,5,7],[1,2,1]] -1

Explanation for Test Case 1

  • This corresponds to the example described in the problem.

Explanation for Test Case 2

  • The given input represents a tree structure, so the total synchronization cost is 17.

Explanation for Test Case 3

  • The given input shows that servers 1,2,3 and servers 4,5,6,7,8,9 are disconnected, making synchronization impossible.