CT56800

The Link Budget of the Wistful beacons

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the lantern district of Glowfen, someone must optimize the storeroom layout. This year the task falls to Bhavi, armed only with the beacons register. 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: 10 37 3 10 1 8 2 6 2 7 6 8 6 10 4 9 2 8 3 7 1 5 2 3 4 7 1 3 5 8 6 9 7 10 5 10 3 5 6 7 3 9 1 10 1 9 9 10 4 8 1 2 2 9 2 5 3 8 1 7 3 4 3 6 8 10 5 7 7 8 4 6 1 6 1 4
Output: 0

Example 2:

Input: 2 0
Output: 1

Example 3:

Input: 100 2402 45 56 47 77 90 91 20 24 15 92 27 71 53 99 22 52 75 86 16 29 9 87 4 24 9 66 64 81 39 57 10 11 52 76 30 49 29 70 65 87 21 26 18 79 28 76 38 46 21 74 67 90 21 92 31 60 1 68 52 89 86 94 88 93 31 93 20 94 14 62 9 98 29 65 28 60 76 93 60 65 31 48 57 99 33 42 55 63 46 48 18 28 59 91 3 55 4 93 17 95 27 68 51 61 72 98 13 50 52 96 78 93 25 61 39 50 30 74 57 75 9 49 1 99 37 80 14 18 22 96 25 94 90 94 52 66 24 97 14 83 20 70 45 93 38 44 49 65 11 72 30 57 64 98 62 80 80 86 87 93 57 58 20 78 28 39 4 36 46 85 8 39 48 49 9 99 1 89 15 64 21 37 7 24 71 78 1 49 13 91 17 77 18 53 31 73 45 94 24 36 44 52 7 40 43 92 29 88 5 94 2 43 33 89 6 90 11 15 10 21 15 40 51 72 29 37 40 61 49 80 23 48 70 72 17 86 62 68 28 99 30 41 77 83 21 77 20 45 67 91 3 60 67 75 82 99 53 75 7 44 26 80 21 56 27 59 37 45 13 79 18…
Output: 0

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.