CT38717

The Briarthorn Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the forest village of Briarthorn close for winter, Keeper must finish the signals ledger - one figure at a time. 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 476 6389 7248 2242 7741 4216 6726 1218 8440 3213 4818 6619 9738 2850 8929 5709 8635 2416 5358 6590 8052 6193 6778 4227 9589 3400 5832 3419 9834 633 7830 2071 4782 543 5201 4755 4966 2537 6521 240 8170 3481 6803 4144 6423 2804 8734 1166 4341 653 1254 2973 9447 22 7048 2337 3084 3192 7530 5173 6429 2639 8450 3800 8319 8952 9162 412 650 169 8700 417 7708 5167 5473 75 8504 6228 6999 2575 2881 1865 6811 658 9055 3190 7485 5056 5583 4337 9745 6162 7977 537 2307 1298 6092 2212 7682 261 2786 4 8966 2188 8689 4069 4132 708 909 4405 8964 6066 8949 5334 6465 2933 6832 1219 5851 7342 7598 2295 7363 1691 2968 1541 2731 2194 7801 3946 7633 1348 1798 2188 2238 3055 8850 1336 8267 4457 8104 1673 7494 7006 8100 5132 5933 4301 6830 382 8036 4482 5606 6214 8498 320 6482 4277 8868 2474 4329 971 3588 184…
Output: 9523

Example 2:

Input: 10000 3301 2866 5283 3945 8675 236 7012 918 9758 1490 5027 529 9747 616 5313 6072 6452 5674 8395 4052 8875 2649 8432 1041 8665 6413 9836 145 688 2933 8721 2795 6097 5251 8958 4539 6686 535 5097 1347 6759 312 2283 2509 6284 328 8489 1655 6099 8538 9616 5279 8912 4238 4724 3602 5892 101 3684 6217 6583 2058 2869 9643 9921 2040 9049 7968 9635 4045 6167 2209 9376 2023 2171 1400 6231 886 8610 6472 9145 1717 8985 3542 4065 4572 6116 275 7580 3899 4283 8396 9381 3231 9084 1233 6353 676 2916 2727 5310 6249 9090 7369 7618 4244 9856 1348 8269 4230 6606 205 4359 8628 9321 425 4094 2199 6476 498 8212 2807 6608 5277 7546 1022 6865 7571 7949 2043 7662 1052 1596 436 6285 2525 9420 3175 5897 4182 9914 1705 1822 5998 8108 2887 8197 6338 7140 706 4764 419 637 56 7279 579 6404 3887 5553 4833 5280 38 8379 4973…
Output: 6698

Example 3:

Input: 10000 2814 1030 6940 6698 7853 1713 8536 4076 5328 3526 7692 3645 9770 2617 4742 723 1191 3909 8266 2849 9019 2842 7257 1253 9158 4931 9499 474 1424 3426 5436 896 9313 3337 3654 105 6383 8416 9613 2156 6956 583 9923 9168 9427 103 1176 4569 8281 5467 6717 8941 9020 1910 8786 4294 8476 1353 7331 3366 9883 4252 9480 2487 2890 1261 8484 808 4170 453 1799 189 2783 2985 6270 1381 7821 7407 9911 36 4626 1940 5021 6119 6297 7312 9545 2829 8317 7130 7471 3836 5585 3712 4093 9077 9265 6535 7378 919 3536 6264 7569 7318 9202 458 5130 1616 4125 4935 7448 3538 4602 4370 9728 3265 9470 29 5260 967 5999 3828 4342 4246 6335 2395 3261 4167 9838 34 5317 396 4733 2367 7130 1421 4580 4690 6927 2487 5362 1508 4457 3814 9441 2935 7497 3379 5824 7200 7512 6986 7505 2527 7412 6858 9178 1282 9068 4042 6020 5218 632…
Output: 7185

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Briarthorn Link Budget - MEDIUM Coding Problem | CodeTikki