CT49941

The beacons at Scriptoria

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Zephyr found an old ledger of beacons in the fish market attic at the ink district of Scriptoria. 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: 100 1666 62 66 67 81 27 40 54 72 60 77 44 98 56 67 24 65 45 81 60 95 43 45 17 95 81 88 5 42 21 67 21 99 1 16 48 90 38 85 69 88 25 67 8 87 69 86 48 69 20 80 28 94 38 97 4 58 12 81 29 70 24 36 38 100 4 80 3 65 44 59 3 5 81 98 16 53 54 73 24 92 45 83 81 85 42 68 7 12 74 75 18 48 24 59 33 39 1 9 67 91 29 88 42 45 18 37 28 68 78 86 39 42 35 92 15 45 32 80 18 99 57 97 23 60 20 86 41 85 10 64 56 96 59 82 4 83 3 61 88 90 12 43 58 77 31 81 41 57 77 88 9 94 53 73 80 98 2 95 35 89 16 92 60 84 4 92 19 41 62 75 54 83 19 71 45 95 27 60 9 99 50 86 9 91 1 32 64 83 13 45 25 48 57 74 16 41 37 96 23 96 50 51 74 86 28 44 23 78 49 90 37 77 25 86 67 78 43 74 19 64 30 64 24 85 25 82 58 76 34 86 50 89 58 90 29 44 76 93 36 84 25 95 18 66 7 54 73 79 28 32 23 76 54 68 4 30 10 79 45 49 27 74 75 97 38 77 26 51 42 78 5…
Output: 0

Example 2:

Input: 4000 999 2563 3824 28 2597 2176 3228 3287 3752 1034 2976 2031 2892 1003 1800 24 918 1001 3856 2167 3217 608 1410 544 3582 1917 3260 288 1034 397 1956 464 2616 1961 3310 531 651 328 2652 2645 2825 2375 3409 392 3661 765 1968 1073 3464 1482 2001 1778 3835 175 1722 2015 2326 1524 1596 769 2132 920 1345 505 935 1822 2153 380 682 115 1958 2964 3366 3627 3871 774 2663 918 1959 312 1926 551 1319 2937 3411 234 1327 3004 3965 2145 3812 2286 3779 245 349 79 3965 1496 3967 1427 2778 1380 3562 842 2805 1070 2454 1175 2858 2628 2684 3243 3278 550 3206 1886 2692 1894 2327 139 202 2693 2740 1954 1973 2958 3536 530 1734 2101 3903 996 3856 669 1539 2920 3299 1655 2948 2877 3162 2950 3399 2648 3999 424 1041 3333 3700 1057 3195 1750 3775 1245 3524 1045 1641 90 3783 1116 1960 975 2840 1308 3768 2031 2440 424 …
Output: 3000

Example 3:

Input: 4000 2033 5 959 857 3868 1637 1701 664 1201 2046 3446 310 1418 1311 2932 465 1284 235 783 2520 2749 3014 3748 957 2343 5 143 533 3420 656 3921 2171 3582 2859 3034 1560 1852 587 1955 1878 2255 517 3977 409 1100 2430 3528 1306 1639 721 2406 1158 2530 2776 2849 2398 2762 1728 2596 187 1932 153 1816 2756 2800 56 3292 1923 3718 1837 2780 579 3393 1566 3037 434 1278 360 2627 755 1394 1135 2393 1962 2957 1615 1627 708 2378 289 2534 730 2460 151 3002 1129 1851 2350 3409 2324 2755 3379 3969 3184 3362 212 3198 2009 3712 1732 2371 785 2368 999 1508 369 745 1661 3779 1311 2724 659 2557 25 1440 956 3174 1655 3583 2441 3497 31 1435 3504 3923 114 1132 78 3749 3121 3520 1837 2502 119 3137 971 3698 2719 3476 294 2036 1694 2208 1236 2632 1426 2847 727 2237 3378 3433 2878 3118 1832 2859 885 1154 335 2392 272…
Output: 1966

Constraints:

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

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