CT40284

Draper's Coral Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Draper the factor watches over the caldera rim of Firewatch's stores of registers. A careful computation stands between order and chaos. 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 1519 13 89 5 77 71 88 12 89 51 61 13 62 59 76 5 59 9 79 7 91 40 51 34 82 10 76 8 30 7 39 14 53 69 74 8 42 13 92 79 83 55 97 20 29 13 28 68 88 24 40 79 80 9 10 62 92 29 69 98 100 45 71 42 99 59 90 49 94 43 54 34 51 20 87 20 56 29 58 30 61 3 13 1 78 21 48 3 52 36 55 48 52 1 6 28 91 68 77 58 86 35 60 15 71 43 83 29 100 40 52 30 59 11 15 30 98 21 24 9 42 27 85 33 72 27 71 36 42 30 72 64 78 11 100 49 68 12 34 43 84 63 91 8 45 26 38 61 92 41 60 11 70 8 68 40 84 23 44 19 81 7 61 28 77 33 46 80 95 39 44 45 61 2 18 66 83 16 56 17 73 52 93 57 62 35 81 67 93 41 55 3 30 61 89 54 77 4 42 35 61 19 91 25 93 10 58 65 70 97 100 1 8 37 63 18 92 10 55 24 37 16 54 26 28 62 75 66 80 5 84 1 7 23 92 53 69 10 70 25 50 23 37 36 100 63 97 18 24 4 17 33 51 8 15 23 45 17 83 44 78 20 82 31 96 59 87 37 65 36 37 23 …
Output: 0

Example 2:

Input: 10000 3390 2650 8259 3513 4187 2905 8637 1762 5739 123 1484 6360 7156 2390 3079 1288 4012 4948 6237 4076 9286 1271 1559 604 8080 6105 9953 728 7912 8479 9151 8982 9887 1949 9645 1276 9390 2932 4665 4951 7540 4258 5580 6136 6398 4160 7947 241 3929 1314 5463 4799 7787 4014 9993 8120 8803 7035 7169 141 6859 4665 5728 4411 8675 178 475 1114 9638 2679 9642 1858 5814 7135 8311 2485 4724 3660 8918 4504 8518 3087 6109 6545 9495 1078 8569 8421 9905 39 1861 5805 8595 3233 9747 2235 9333 5663 9059 2648 8342 2280 4131 427 7283 3014 6232 189 5472 2970 3927 1318 4910 1057 5686 3969 4627 4658 8262 2048 3049 1421 3095 8419 9244 5309 9381 2131 7303 4403 7271 2612 2841 1140 3076 6680 8645 4862 5639 4711 4887 5492 8657 3698 5638 2418 6433 6205 9212 1115 2432 8443 9037 8260 9406 4457 4474 4729 8317 996 5533 3…
Output: 6609

Example 3:

Input: 10000 1211 2327 3618 6045 8614 2693 6273 774 4361 2440 5684 8530 8812 4852 7499 5333 9644 2489 8863 4867 6662 2725 7862 1173 3537 792 5319 5305 8269 7958 8895 4341 8957 6914 8780 2902 8516 429 7258 3803 5674 6700 9743 6152 8363 7709 8592 1257 1370 1393 5608 7637 9708 593 7069 3564 5758 3947 7598 3755 9387 287 912 5954 6760 2398 8481 1793 4473 3587 9688 7729 9429 6186 6569 2926 5444 382 4927 9619 9903 2443 7406 85 7129 6578 9045 3481 9621 2070 2754 1754 7869 2182 8657 2989 4720 3529 5693 284 8448 170 3574 2002 6125 63 5040 1557 3490 6319 7380 4466 4850 2094 4763 2024 5317 3620 6703 6389 7954 9636 9952 4588 6343 137 6369 7960 9973 4203 7106 5670 9041 3240 7190 680 5365 1547 3834 4366 5962 546 7711 4451 6747 2239 5396 3690 8626 6237 9012 1861 4826 6256 6678 3468 7630 2470 9178 1898 2796 5089 …
Output: 8788

Constraints:

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

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