CT52068

Paige's Link Budget Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Paige runs the chandlery at the foggy moor of Greyfen. Today the books show a list of registers, and the numbers must be worked out before sundown. 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: 10000 2513 6369 8844 3723 7132 427 3190 3885 6327 394 5692 6778 7241 6 8745 2678 5902 1130 6171 2592 7894 824 3612 555 3020 4397 9867 6904 9250 4560 8901 193 920 1051 6785 3677 4920 337 7683 2798 7148 950 1438 1634 8647 1530 9108 8644 8738 9745 9860 1044 8606 815 5195 394 4519 5139 8498 7557 9755 3217 6070 7478 9619 5993 7150 3562 9571 4976 5229 2950 6086 1811 4296 3150 3292 2657 5689 1258 2840 4244 6291 1137 7033 2366 9283 6284 9527 4180 6177 5273 9776 6203 6607 2452 2960 3333 5928 5068 6595 1207 4374 7018 8829 1082 1808 6231 7036 2455 4230 955 8844 8064 9050 5420 5816 440 6509 5970 9427 2733 4267 342 3087 6422 8148 2509 4852 1672 6736 9736 9781 3339 6583 706 804 1404 4373 2286 8839 3275 9212 6199 8488 530 2982 5099 6549 1642 9070 4242 8453 959 8996 4719 7609 4145 5826 1671 1980 6317 6942…
Output: 7486

Example 3:

Input: 4000 187 52 2463 1148 2599 461 1238 273 2993 987 1975 1394 2617 962 2852 1323 3098 2143 3714 2107 3643 1832 3569 1287 2009 2857 3208 1094 1809 738 3064 483 708 435 2661 392 2810 3728 3841 773 2643 721 3985 867 1042 349 3546 3344 3439 2688 2825 364 753 325 615 831 3293 1451 1500 377 1242 1218 2941 3062 3080 1201 1542 426 2921 439 1003 1365 3108 765 2333 1593 3380 2355 3134 333 462 2021 2654 1312 1381 2101 2832 1018 1876 1411 2489 1658 1755 2427 3352 821 1983 539 2575 613 2565 193 738 3243 3253 1720 3836 209 1225 626 3592 2315 3715 1049 3671 81 2246 3216 3451 2517 3088 1569 1732 353 1408 1063 2064 962 2672 922 1078 1965 2355 374 2207 1583 1782 3102 3448 150 3224 140 1549 1439 3656 436 2787 1198 2810 856 2658 483 2575 1617 2967 2108 3216 921 1318 1959 3838 1770 3818 3945 3986 423 637 955 1741…
Output: 3812

Constraints:

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

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