CT38439

The marks Link Budget Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the gristmill of Rye Hollow, someone must tally the donation drive. This year the task falls to Zane, armed only with the marks register. 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: 4000 2158 2493 3248 523 3725 267 3978 1397 3775 507 3910 1953 3186 325 1545 1779 3057 692 3451 1333 1562 580 3461 230 3800 241 392 2247 2895 2620 3387 1488 2948 64 279 2463 2631 127 2313 86 226 1138 3436 3066 3135 1226 2244 364 575 279 325 668 3996 1283 2989 668 850 1904 3436 2872 2958 956 961 2264 2718 196 211 522 2155 1941 2681 367 601 1410 1751 781 2385 146 988 1043 2403 650 1134 1058 2974 523 1353 712 1888 527 3850 891 3010 2693 3405 105 3346 1873 2880 510 2780 844 2009 1490 3057 950 2080 2124 2392 608 2015 207 2941 586 3015 2133 2904 1275 2537 699 2631 1180 1486 530 1099 435 2297 1107 1852 582 1545 61 2230 1236 1329 1970 3486 1138 2340 1775 2662 642 1847 2286 3319 1819 2107 150 3069 53 266 74 1223 1557 2489 2939 3271 1948 2932 822 1784 502 3099 2254 2358 918 2678 2945 3912 447 1724 30…
Output: 1842

Example 2:

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

Example 3:

Input: 4000 228 357 2187 552 2819 413 2495 1219 1918 1720 2505 1110 2139 1189 3207 1967 3247 579 3262 541 2871 2297 2360 1005 2836 2694 3193 94 3888 1129 2235 1353 3078 2574 3173 1326 1771 1185 1206 2870 3984 1042 2126 195 3345 147 608 39 798 2973 3566 1114 2751 2083 2643 3308 3899 317 1262 1007 3175 74 618 539 3910 2231 3994 1613 3834 684 2286 2795 3262 408 3164 2603 3628 128 3396 1267 1580 1317 2707 203 2174 873 2557 477 3596 2457 3289 1164 1981 9 3656 1720 3057 896 1921 1594 2615 418 1422 732 1821 1628 1872 328 2533 2976 3813 1155 1970 1212 1260 1741 2972 601 1867 625 3220 594 902 1594 1788 3515 3777 3142 3220 44 995 1488 1853 244 248 1155 2654 3504 3510 144 2275 903 1563 2225 3247 1762 3555 2390 3709 879 1531 1871 2988 922 1697 2594 3839 3573 3708 2408 3335 612 2818 637 3846 1570 2701 832 354…
Output: 3771

Constraints:

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

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