CT49366

Quartermaster's Link Budget Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the lantern reef of Glowtide as Quartermaster unrolls the day's manifest of beacons. The tally will decide the next shipment. 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: 100 1253 53 58 24 92 59 84 42 66 46 78 55 93 38 45 40 82 58 95 24 75 37 89 56 93 49 54 30 71 33 51 10 81 6 60 9 41 61 90 79 94 82 97 59 79 15 44 6 79 85 91 8 80 22 25 24 81 59 87 5 75 43 57 70 92 35 81 51 63 67 84 36 81 55 64 57 75 4 82 21 43 55 69 51 54 35 62 19 98 60 69 28 37 47 54 23 71 26 64 3 10 24 73 57 67 69 80 11 33 14 62 26 35 27 96 25 78 3 42 48 91 1 75 21 90 42 93 51 75 18 64 63 75 46 97 10 32 62 80 53 97 1 27 39 67 18 24 25 38 33 50 56 85 16 19 21 34 51 53 46 80 1 19 15 70 15 97 2 45 19 99 5 93 4 64 27 66 60 100 1 91 35 97 1 70 57 60 21 65 65 77 26 69 1 20 58 62 22 94 19 23 36 97 18 20 25 96 65 88 71 90 29 43 49 82 25 76 5 72 6 74 35 86 2 21 70 85 4 71 6 95 12 73 8 94 66 100 13 19 10 77 29 97 7 92 93 99 11 86 48 59 81 83 76 97 39 47 4 52 11 92 26 60 6 67 9 37 9 81 90 98 14 16 9…
Output: 0

Example 2:

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

Example 3:

Input: 10 7 6 9 5 10 1 5 1 8 3 9 5 7 1 3
Output: 2

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Quartermaster's Link Budget Ledger - MEDIUM Coding Problem | CodeTikki