CT42198

Last ledgers of Aldo

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the tulip beds of Bloomhaven, Aldo the auditor keeps careful count of the ledgers. Prepare the guildmaster's brief, every figure matters. 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 1020 1329 2633 1720 3486 2293 3942 114 1796 133 2092 1404 3144 775 3791 1365 1630 520 2684 428 543 1399 2023 2879 3848 824 1736 55 3296 2346 2928 1204 2997 879 1092 503 1375 2158 2181 3304 3999 175 757 21 3851 1509 3074 1394 3905 1428 3875 1806 3217 1802 3636 315 1154 414 2152 2264 3464 153 315 798 3811 1935 2646 1964 3888 838 2343 2314 3394 1054 2804 1887 1951 3454 3541 37 3155 484 1530 1199 3696 1037 2668 1416 3722 2555 2733 162 3962 2749 2988 559 944 1891 3473 65 3509 782 2965 1232 3117 1100 1548 2422 3510 1349 2002 3358 3715 1029 2061 2283 3014 912 1584 1614 1767 470 2198 548 628 964 1160 491 685 630 1611 1614 3464 3336 3552 3081 3684 567 2089 218 724 3629 3969 757 2379 1750 2331 1145 1647 559 1695 730 1569 1564 2494 968 1775 238 1313 1347 2115 1410 3195 1505 3253 970 1697 916 375…
Output: 2979

Example 2:

Input: 4000 141 532 1188 896 1860 2528 2546 1589 3726 67 3091 3669 3944 1059 3623 2232 2486 230 641 2577 3599 27 783 2222 3697 1185 3836 3060 3509 2614 3338 496 887 2165 2762 17 3519 603 746 1662 3344 1626 3397 600 846 786 2501 1581 1600 950 1888 2561 3556 560 1729 1019 1110 958 3136 139 2254 2294 2715 1011 1885 522 2510 1667 3347 1092 2478 1761 3156 1120 2657 594 3417 139 3878 588 2689 1469 2560 827 3045 562 2442 2445 3835 1636 2255 471 1798 680 1848 719 1870 2109 2312 2747 3963 845 2597 2717 3199 2142 3354 690 2152 1086 1747 1448 2134 1823 2101 529 3984 1213 2402 3382 3902 540 1359 988 3529 630 1726 1022 3387 1593 2855 226 308 2609 3051 1624 3557 2643 2714 575 1518 93 579 484 1446 2353 3838 599 3540 2976 3848 507 3380 916 2098 651 3422 745 2126 679 3852 40 2003 436 1990 2067 2413 1546 2478 393 …
Output: 3858

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last ledgers of Aldo - MEDIUM Coding Problem | CodeTikki