CT41597

Ysolde's Vermilion Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the cliffside roost of Stormrest opens only for a perfect tally of registers. Ysolde 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: 10000 1789 1778 8803 3808 8876 1423 3713 2479 6696 3908 5759 3216 8202 3489 7820 7555 9474 6487 7423 5859 8850 472 9322 3330 6559 5805 6573 5954 8778 1835 9470 2483 9491 3366 4864 5892 8250 1976 5905 1361 1670 2642 6206 477 9665 1987 7203 2670 7501 591 4221 3986 4021 3470 9799 4434 8615 8363 9342 5932 6432 3471 7384 58 5634 1021 5604 6885 8686 6973 7367 1640 2757 962 6098 1039 7826 3771 8451 3606 6963 1438 8457 1511 4737 9197 9763 488 8105 3471 6058 972 9247 2443 6043 5822 7797 6765 9581 8625 8988 592 1708 5332 8455 5824 9659 5838 8526 6516 8889 1226 7538 2513 3936 3258 7186 502 5777 1996 2517 318 6977 8467 8906 36 6290 5613 9151 230 1873 2070 5871 9393 9977 3631 7119 3398 4738 1820 4778 53 2548 1329 5135 1366 9073 551 5294 1367 2114 5920 9461 116 8278 77 8485 178 3067 1378 7232 1418 9904 …
Output: 8210

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Ysolde's Vermilion Ledger - MEDIUM Coding Problem | CodeTikki