CT56208

Peddler's Golden Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The store warden Peddler has been asked to audit the season's records. On the desk lies a long table of marks readings. 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 1692 1002 2911 322 1156 625 3831 929 3564 66 1777 1304 3236 1791 2911 3396 3674 750 1323 985 1694 1392 1580 24 243 1074 3994 998 3106 2890 3874 140 3266 2064 3703 1307 3225 822 3833 2766 3521 165 2540 2033 2808 1959 3087 945 2354 2196 2333 586 3082 3135 3625 3791 3871 915 3751 1201 2276 596 2205 89 1288 1696 3285 2382 2402 82 1856 1597 2579 1489 3008 922 1464 1808 3307 323 2232 857 1250 749 909 717 1446 2877 3536 1119 2068 466 787 466 2173 2410 3302 23 2521 734 2228 1701 2021 260 1776 922 3994 754 2266 1615 1802 1710 3997 378 497 1134 2742 167 551 1943 2616 2222 3955 1074 1172 1069 3578 318 1176 2644 2790 2191 2982 224 2950 1048 1146 1449 1680 2637 3511 653 2339 1712 1905 800 3259 921 3036 649 1879 33 2502 1331 3090 582 1158 1753 3901 1789 1876 2681 3209 2615 3136 1149 1767 333 3390 1…
Output: 2307

Example 2:

Input: 2 0
Output: 1

Example 3:

Input: 10000 3865 1383 4712 4768 7430 120 5571 369 4565 3427 9523 5889 7281 3500 5883 4081 8237 1705 4568 519 3290 179 6822 3832 9962 9163 9917 2592 9341 602 764 6527 7015 1544 6430 4677 4874 5848 6598 3414 4755 1149 4006 3749 8404 1805 6927 918 3597 4452 7420 888 8030 1020 4014 2877 9533 4009 8296 5552 7585 3030 8253 1547 2512 5661 8639 8823 8906 266 2292 291 7049 6474 6791 2262 5139 4111 5711 4122 8964 425 5684 1738 4861 1563 4084 2212 9913 629 5650 2629 7813 1441 6059 1720 1741 7224 7527 1356 9659 586 1219 671 9311 1749 8726 322 4947 2273 2986 2692 3954 4754 6247 2245 3648 4354 7553 4048 8968 7335 8216 1801 7319 4298 4657 670 1821 3059 4698 1543 5584 118 6580 423 4065 7020 8199 1094 1151 1100 2367 5527 7668 3388 5513 7928 8647 194 7943 4022 4711 8305 8770 1471 6011 3795 5222 935 8821 487 5783 …
Output: 6134

Constraints:

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

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