CT51400

Vesper's Sterling Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the peat bogs of Mossgrieve, someone must tally the donation drive. This year the task falls to Vesper, armed only with the signals register. 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 2262 137 1366 479 2161 1488 2030 492 1881 1778 2683 864 3733 2987 3862 2811 3138 2628 2925 341 3626 2455 2687 1249 3587 1453 2134 1624 2541 1911 3711 3031 3785 1484 2591 1195 1984 38 2974 1200 1666 125 2397 1504 2439 261 3587 1864 3804 425 1242 3394 3929 3590 3728 1171 3042 1528 2795 535 822 36 1741 1873 3970 1645 3299 75 542 1263 2175 136 3110 1793 3365 397 653 2294 2971 1184 3027 878 3928 757 1843 57 3528 1579 2051 1670 3159 1900 3485 1301 3118 321 2285 1295 1772 1626 3259 1675 3303 1478 3724 1277 2094 1268 2356 505 3086 1988 3851 2246 3442 2970 3484 700 1012 2342 3037 151 878 590 2234 1026 2505 2220 2865 1549 1629 3016 3513 764 841 229 2149 380 3971 2960 3443 2946 3151 2438 3379 2563 2736 315 3272 819 3109 1807 3285 418 675 2298 3593 982 3942 2307 3127 1692 2289 3282 3564 812 3789 …
Output: 1744

Example 2:

Input: 4000 2552 639 1158 344 2548 967 2934 2688 3435 318 1549 1853 3800 1309 2171 2544 3577 2400 2997 1030 3824 296 3602 1477 2428 1479 2501 1279 1824 1592 3879 884 3953 1632 2644 1551 2738 3369 3484 1712 1865 1095 3216 1230 1819 219 2924 37 3619 358 428 3427 3858 342 1007 1486 1995 76 3960 207 3963 1339 1856 559 3639 1823 2551 626 1154 973 3309 233 3850 217 2279 3543 3583 3095 3624 2033 2735 2593 3553 380 503 1346 2051 2006 3761 1265 1775 1536 3757 3475 3890 2276 2468 2237 3486 800 2952 2454 3752 1405 2508 1956 3113 1744 2708 2387 3338 190 826 751 917 1842 2097 1693 3306 1522 3902 664 680 1111 1323 195 1794 2374 3919 1382 2507 237 1034 911 2153 49 3769 3181 3370 328 1975 936 2212 2116 3126 2161 3313 1285 3062 180 1846 1219 3144 53 3366 1978 2197 1742 3464 2538 2651 272 620 920 3765 1657 2464 10…
Output: 1485

Example 3:

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

Constraints:

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

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