CT53289

The Link Budget of the Ruby beacons

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the steppe camp of Horselord Plains opens only for a perfect tally of beacons. Galen means to find out. Task: n isolated nodes are joined by m edges (some may be redundant). Print the minimum number of additional edges needed to make the graph connected. Input format: First line: n and m. Next m lines: u v. Output format: Print the number of extra edges needed. Constraints: 1 <= n <= 4000; 0 <= m <= 4000.

Example 1:

Input: 2 1 1 2
Output: 0

Example 2:

Input: 100 69 45 63 44 52 10 72 27 34 27 44 2 71 53 86 13 16 32 86 9 26 13 99 20 96 23 72 2 15 35 76 85 96 2 93 18 52 67 94 62 94 38 78 53 58 37 57 38 64 27 56 49 75 15 41 74 78 39 57 89 100 23 70 32 75 4 31 33 77 30 61 17 74 24 64 62 79 18 53 18 98 25 74 3 62 17 21 65 74 17 53 63 88 79 97 69 99 6 29 20 74 19 42 83 90 31 36 92 97 19 58 13 48 30 79 60 100 52 76 5 43 7 71 29 62 36 77 14 53 37 83 29 98 85 89 14 74 5 49
Output: 31

Example 3:

Input: 2 0
Output: 1

Constraints:

1 <= n <= 4000; 0 <= m <= 4000.

Loading...
Test Cases:No test cases
No test cases available.
The Link Budget of the Ruby beacons - MEDIUM Coding Problem | CodeTikki