CT48523

The Caramel Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the northern keep of Frostgate, someone must price the new merchandise line. This year the task falls to Pia, armed only with the ledgers 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: 2 1 1 2
Output: 0

Example 2:

Input: 4000 1340 589 1581 1427 3866 1078 1264 2827 3544 238 1998 1421 2105 2915 3207 3455 3835 736 1198 1962 2901 1645 1786 1400 1927 1052 2477 2272 3057 534 1565 770 2331 1051 3563 3256 3371 1579 3591 122 2053 2332 2954 3225 3798 3069 3366 2418 3861 2921 3054 372 2913 644 3849 9 3955 1964 2822 1663 3333 2820 3975 2759 2926 1382 1426 1848 3854 713 806 3237 3929 493 3732 2345 3141 1764 3366 2037 2566 474 921 1751 1787 654 2053 965 2756 1403 3368 2915 3539 2240 3682 1316 3530 431 778 2665 2852 2092 3904 877 2202 2593 2874 2307 2967 2878 3772 591 2917 1268 3981 573 1966 260 2517 344 2557 1207 2818 2609 3769 1137 3632 510 2868 482 3117 157 1018 3617 3745 208 873 436 3482 591 1571 994 1372 3608 3665 1257 3182 2417 3628 519 3431 1915 3973 1725 3755 257 2949 909 3323 2967 3504 1927 2381 346 3643 2999 32…
Output: 2659

Example 3:

Input: 10000 2196 7254 7264 114 1936 958 5975 1764 5301 3565 8579 7442 8569 6633 9479 2758 7555 1699 7683 7630 7947 580 2465 2139 4024 2834 5019 9226 9346 6276 8859 11 7119 6679 6829 2975 4832 375 5272 1530 8771 3324 3922 3278 9010 148 2428 3309 3870 3179 9912 2276 6855 3815 8323 1374 7057 1059 4864 2273 5108 7750 8935 5125 6311 2434 5982 695 3578 1617 4076 2886 3418 5991 9344 815 2039 7088 8182 320 2793 4863 5752 6545 9628 804 9762 1766 3492 182 5963 6917 8898 5668 9272 1719 3513 783 1320 7640 8740 7038 9165 5243 6049 3122 9360 2412 6383 7250 7486 1134 8900 963 1406 5219 8277 1779 6622 3543 4566 1056 2118 2426 4045 2998 8377 2320 4544 6157 6611 9725 9787 2999 5528 1715 5511 1246 1857 896 8218 132 754 3338 6617 6419 7437 3582 7270 3629 3869 493 8168 4541 7431 6164 6818 6683 8089 1912 6831 3201 53…
Output: 7803

Constraints:

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

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