CT37624

The Link Budget of Thornveld

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Dorian runs the shed at the acacia flats of Thornveld. Today the books show a list of beacons, and the numbers must be worked out before sundown. 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 145 1 11 32 55 46 96 2 62 6 97 21 85 20 76 60 96 51 73 25 67 31 98 33 80 92 100 28 64 1 29 1 69 66 67 17 85 37 49 71 79 48 75 10 32 21 47 41 90 55 90 24 88 29 98 23 55 54 60 51 65 31 76 7 93 41 96 27 63 60 70 13 58 19 29 5 73 16 59 46 86 23 66 45 92 3 91 14 69 14 50 15 33 36 80 7 56 22 65 52 61 74 86 42 56 11 44 79 80 74 94 59 96 45 59 43 84 9 98 43 85 34 61 15 18 20 57 9 15 33 55 56 82 4 74 7 68 49 72 46 82 20 24 32 100 56 67 54 83 31 65 68 70 20 38 12 77 87 98 33 64 11 98 20 99 33 61 11 57 31 73 7 43 1 73 47 70 78 92 3 52 17 51 56 87 1 14 83 95 72 94 20 32 60 71 32 50 53 62 72 84 42 78 36 43 35 82 24 63 51 75 33 35 38 99 45 50 20 56 4 39 36 76 50 67 43 72 17 93 30 99 16 82 24 48 22 74 62 65 47 69 7 59 49 85 14 98 39 49 26 36 6 46 18 55 16 31 9 97 36 62 43 50 20 27 6 24 15 98 54 86 23…
Output: 5

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 Thornveld - MEDIUM Coding Problem | CodeTikki