CT52947

Diya's Link Budget Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the glass towers of Prismhaven as Diya unrolls the day's manifest of marks. The tally will decide the next shipment. 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 3341 407 3545 2350 3414 2143 3950 3034 3095 328 3672 414 697 2348 2783 3257 3938 1326 2937 1535 1752 239 1348 510 799 576 3807 2998 3535 2853 3050 1017 2161 1508 3635 394 3531 1645 3960 1846 2596 2105 3797 492 1109 390 1114 292 643 674 2873 27 689 122 255 656 2775 164 1817 462 3581 1966 3724 2130 3299 1036 2348 1317 2260 751 3946 133 171 570 990 1118 3946 1206 3949 419 2715 505 3085 442 3308 2274 2436 3580 3781 753 2972 1702 3489 3123 3930 912 2936 1122 1343 2324 3965 2311 3311 1697 1805 1016 2001 1396 2225 159 3165 439 2611 384 3998 1771 2320 1431 2008 926 1362 190 629 1311 2977 657 725 1393 2196 762 3600 83 2962 746 803 218 3219 1713 2196 318 992 1364 3624 796 1135 653 1058 203 2566 849 1820 1687 2855 1906 2413 2237 2730 1386 3171 2558 2617 1164 2395 2231 3997 1429 3306 854 2162 109…
Output: 964

Example 2:

Input: 4000 683 2610 3669 94 1311 1960 3637 373 2063 1919 2204 2592 3275 1675 2110 392 744 1822 2838 1917 2980 2278 2659 1483 3393 693 3175 141 711 2943 3539 2575 3500 2172 2476 1783 2321 3094 3470 2457 3731 303 651 64 1407 1938 1961 1338 1420 1204 3770 1030 1681 1984 2486 3293 3500 2562 3488 464 2259 1978 3935 3064 3600 3016 3708 635 2879 858 2530 1422 3172 1606 2102 948 3082 1530 2480 562 3546 1218 2556 152 3276 998 2047 1302 3018 64 2197 1825 2798 1257 3625 629 2025 494 2595 1874 2736 2436 2679 295 1767 679 1572 322 1374 3346 3827 1017 3451 295 2917 984 1967 1684 2928 915 2178 618 1799 1876 2590 864 939 2084 3837 1372 1991 488 495 2600 2982 1179 3921 38 92 2233 3463 2198 3308 383 2644 1898 2663 1371 3403 944 2447 2412 3786 477 2357 527 625 1010 1143 609 2489 802 867 2153 3517 1644 2385 273 158…
Output: 3316

Example 3:

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

Constraints:

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

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