CT50280

Yusuf's Link Budget Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Yusuf found an old ledger of ledgers in the observatory attic at the crane marshes of Stillwater. The margin notes pose a precise question. 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 2815 430 8130 7931 9727 5512 9522 4764 6374 434 9927 6210 6870 3232 9150 4973 7700 2662 5328 2673 4545 5066 6118 861 4621 4723 9069 3010 6694 8234 9111 1508 5469 6634 6753 127 9381 1792 6002 4303 8926 1716 8459 1321 8714 3018 7553 544 2139 2325 7857 1186 2494 859 7155 4106 7449 8448 9543 5015 9757 1087 6578 3231 7405 2107 6960 6580 9802 5097 7822 4765 8893 4879 8628 2817 5082 2952 9675 124 353 5539 7933 2465 2955 3227 6500 7294 9445 3789 4829 4993 5886 923 4943 3077 9854 7303 8090 1150 7094 3359 9574 3088 8522 2947 6391 8627 9410 7029 9384 4911 8588 6371 9349 6570 7491 3433 9977 7960 9156 749 1449 7891 9667 259 5330 2857 4264 718 5117 4340 9319 1960 4956 4698 9489 1189 2174 3676 3891 1348 3355 7865 9545 2939 9403 3111 8661 5769 6085 2110 3280 6948 8879 3229 5189 1935 8340 4573 7409 5…
Output: 7184

Example 2:

Input: 10000 1221 2603 7662 6748 7101 719 5071 8300 9040 8817 9835 5918 6471 6929 7122 4209 9428 3479 4354 2081 4669 1244 7574 9040 9531 2801 3435 2747 9735 5631 8057 2333 4382 1596 3600 1809 2973 2082 6675 6488 6555 2931 6881 1484 4308 3461 8694 2795 5313 3004 7109 3735 7361 6643 6709 629 2085 3143 5943 8585 9911 3484 9472 8632 9141 4013 9244 2598 5444 4940 9227 2332 8917 2607 2900 5504 8736 1895 2889 3666 8071 5825 6899 1089 4474 2808 3850 726 7325 1375 8905 3857 7949 1955 7173 4487 7790 51 7817 3350 3626 4830 5807 3157 8598 2029 5605 269 1867 6409 9373 5898 9211 886 1371 3596 7296 268 4327 450 9489 861 2990 538 2401 5215 6115 3271 9808 6332 8602 3680 5541 952 4630 1564 4166 3121 3538 5465 8401 2817 5009 4607 6440 4916 9647 1201 7581 6128 9269 7696 7948 4009 8710 7588 9694 8957 9595 3259 5283 1…
Output: 8778

Example 3:

Input: 4000 2298 51 86 2541 2843 344 3053 1429 1959 456 2090 1923 3099 235 376 762 2764 2073 3238 2443 3797 2437 2794 2145 3006 1912 2568 2845 2912 2192 3224 111 1726 2190 3930 468 2008 882 2457 228 1266 1668 1974 456 2720 120 3376 793 3758 2189 2227 765 2875 2572 2743 551 2995 532 2892 1255 1453 907 3823 1182 3356 322 1055 1160 2878 2203 3577 2983 3949 1290 3395 3027 3275 1284 1443 414 1267 997 1600 1227 2939 1413 3906 853 1170 2413 3873 82 3666 2314 3791 188 2809 1114 3186 1805 3784 2537 3124 1206 3794 1590 2439 362 1843 160 229 425 2941 996 2215 387 2842 835 1688 477 2688 800 1613 2575 3425 3085 3255 791 2748 2617 2657 1551 3405 2366 3347 175 3113 1925 2430 197 3137 2697 3647 196 2011 1602 2022 1317 2119 766 3313 3114 3848 2119 3640 840 1010 384 1987 1677 3530 3076 3792 219 1135 3230 3481 336 …
Output: 1705

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.