CT41814

The Link Budget Beneath Firefly Mere

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the lantern lake of Firefly Mere with crates of beacons, and Admiral the log keeper 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: 4000 3615 491 3937 144 1308 1942 2267 1829 2026 2217 3635 2026 3492 247 2672 215 2913 1052 1990 432 1310 759 3467 1253 3262 2935 3962 1807 3205 63 2442 498 943 1366 3034 2594 3646 354 2720 1023 2143 2443 3467 1522 1876 1843 3085 391 2381 1553 3573 954 2443 1050 3982 639 3216 296 3811 3483 3834 874 3807 1137 3107 816 3144 1357 3357 1819 3458 930 2970 2069 2548 836 1190 1849 3402 1201 2415 1694 2581 3016 3067 1443 3112 1811 2896 2173 3727 932 2276 1930 2524 954 2843 2755 2805 1331 2622 1016 3554 1143 1861 693 2108 1104 3328 1597 2858 1511 1728 63 3591 3462 3791 1604 2990 2292 3355 931 1757 1904 3871 1747 2413 38 3761 506 3684 582 3913 3064 3244 905 1607 924 1928 2826 2937 300 771 1711 2748 2861 3603 992 3610 2594 3819 1276 2685 1507 1973 505 3626 256 1515 787 3372 1519 2912 1864 2468 1031 34…
Output: 841

Example 2:

Input: 10 42 6 8 1 3 4 10 3 8 3 10 7 10 8 10 5 8 5 7 1 2 7 8 3 9 3 5 2 7 4 7 2 9 5 10 9 10 3 6 8 9 2 10 6 7 2 8 2 5 2 4 5 9 4 8 2 3 1 10 4 5 6 10 1 6 6 9 1 9 1 4 5 6 3 4 4 6 2 6 1 5 3 7 1 8
Output: 0

Example 3:

Input: 10000 2535 4172 5365 8705 9988 3412 5448 5822 9446 734 6889 2509 6696 2081 6959 1908 7152 6302 7795 7030 9883 149 8772 2068 3486 1145 5785 7201 8240 1835 7407 6763 7924 5191 7887 1086 5573 4785 8202 7113 7495 3231 6826 3815 6990 2889 3431 5846 7944 5961 8067 6224 6528 3398 7474 3948 9745 4001 6430 111 4342 3994 5731 1510 4792 1372 2207 4759 6093 3622 4570 2841 7188 5740 7196 2883 3536 1998 2076 900 6305 789 6422 3614 6905 2010 8457 3009 6492 4833 5756 6135 7382 5270 6334 5390 9831 364 9853 3481 6905 4774 5295 7814 8487 7008 9859 845 8521 2802 4473 3579 4137 3225 5423 7326 9473 6561 9091 2720 8149 3525 7919 5054 5688 5363 6664 6104 7151 608 6254 2174 2697 2860 9304 4741 9181 3904 6852 5959 6739 976 7230 4541 4833 3043 6495 503 6644 2817 8037 6967 8386 6672 8023 477 1980 3571 6547 25 1193 12…
Output: 7464

Constraints:

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

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