CT46734

The Link Budget at Lodebarrow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the silver mines of Lodebarrow with crates of marks, and Cleo the assayer must account for every last one. 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 3702 301 3370 422 909 2720 5995 5615 7916 5739 9859 120 2979 2195 5799 6702 9334 4151 5678 5038 5578 3748 8175 402 1653 9107 9367 1154 7560 1945 5101 906 8083 336 9810 8580 9459 4850 5879 7 814 1407 2977 2455 7491 3149 9444 2219 5826 5191 8261 5137 7939 8828 9716 9198 9696 286 2561 1473 4642 1106 5238 5286 5402 2778 9437 1828 6011 278 2942 3218 3255 4975 9632 3843 9305 1625 7999 6560 8420 1103 6706 2668 7427 26 6857 4727 6654 1158 7802 6161 6723 8102 9549 8799 8920 6123 7264 1428 9910 1146 8447 2422 8425 5647 8472 2508 9227 2586 4964 3898 7145 351 2258 5398 8770 985 8396 6989 9884 530 7791 323 2476 1868 4718 3635 9743 6933 9807 1445 1964 889 9003 5313 6725 2882 8216 3385 4761 1524 4666 2132 3809 2348 5362 7211 9052 3989 4941 239 284 6223 8054 4836 8075 6296 6660 1083 8155 1105 3244 1…
Output: 6298

Example 2:

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

Example 3:

Input: 4000 1449 373 3213 1165 3252 2824 3776 3630 3811 3351 3648 11 3457 879 1148 287 3209 1907 3893 153 3603 3185 3776 485 2901 1661 2425 529 945 1551 3540 1099 3331 1080 2831 125 2293 2184 3037 1125 2527 394 3208 2585 3163 858 1764 2477 2854 2483 3696 267 1835 325 2786 1024 2427 1464 1936 1145 3189 2389 3900 230 3642 1434 3431 1340 1758 1149 1703 2766 3860 3184 3502 1367 3687 1716 2309 2498 3960 588 1350 1195 3641 1464 2736 1410 1645 2242 2690 1912 2416 2911 3951 1625 3029 67 1702 2788 3242 1654 1876 2182 3543 3086 3154 2245 3747 3372 3596 2403 3716 3469 3991 169 1063 703 2095 2018 3863 28 114 446 1867 1708 3400 2741 3358 344 2304 136 3745 1820 2048 402 2929 1658 3879 1171 2387 31 1422 567 3845 1629 2956 323 926 1690 3047 637 851 106 443 1948 2939 1400 2565 343 1433 3543 3933 2073 2677 1291 26…
Output: 2550

Constraints:

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

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