CT50857

The Link Budget of the Opal ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the salt flats of Palemere, Curator studies rows of ledgers entries. One clean number will settle the guild's oldest argument. 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: 10000 3943 1829 7743 1387 9378 6833 7378 506 6980 3017 5507 2172 9881 2791 6400 4747 6555 1086 8797 2528 5420 5216 8894 706 4515 4721 8477 1571 2977 1927 5773 2987 7951 4326 4803 2935 6809 8813 9654 4746 8385 3682 8758 2579 8948 3186 9914 8063 9899 313 6593 8305 8819 807 7022 4222 4505 371 1218 7425 8046 1623 4821 6836 8954 6723 8856 5342 7190 8871 9294 1614 5549 668 9281 1352 7730 3345 9265 1917 7721 2097 7183 2825 6540 5944 7222 5421 7427 1804 6349 2334 8450 6086 6657 1773 4712 154 1351 4071 5945 4820 8352 2002 3437 1093 3967 2809 5446 4139 7060 274 6937 930 3666 1626 6158 8239 9075 1076 3924 2284 6327 5056 7128 1925 7489 90 2324 424 9716 6553 8541 194 9749 2074 2837 608 4057 5060 5859 4514 5104 6421 8706 211 3446 2087 7041 5044 7800 1860 7131 3899 9930 2699 9728 2772 3659 5000 6476 5856…
Output: 6057

Example 2:

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

Example 3:

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

Constraints:

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

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