CT43073

The registers at Glowfen

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Captain inherited the boathouse at the lantern district of Glowfen along with its curious bookkeeping system for registers. Time to make sense of it. 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: 10000 590 1233 8740 3507 6593 5880 7110 2241 9656 152 4597 169 2167 4097 7736 1360 9776 4710 9769 688 1989 2567 4997 1400 8321 3491 4393 75 9410 392 9753 793 6421 1917 5492 2897 5849 3347 6662 1025 3017 3292 9119 1196 5493 937 9922 4990 8884 3912 8862 5147 6739 7768 8245 723 3688 4034 5790 2965 4540 5123 5620 97 913 995 5040 2766 4950 8163 9953 7038 8250 682 5739 6909 9306 5815 6681 4076 4381 4853 7891 1018 9551 432 1853 5737 6118 675 8627 2462 8998 3301 5239 3548 8523 1074 8380 4101 9809 2549 6418 1921 6853 722 1269 3286 7011 3520 4270 3839 7078 4668 5643 5068 9160 2152 5528 6439 7721 4107 4183 5695 9305 2373 9438 4956 6543 7941 8847 4265 8868 3773 7888 4511 6652 4676 7891 9289 9430 3407 9919 188 201 8956 9859 5110 8205 3561 9014 2084 5667 5514 6164 4034 7625 7590 7818 1278 9892 722 4781 …
Output: 9409

Example 2:

Input: 10000 2055 5665 6595 4503 5432 2016 8285 7153 9860 353 8827 377 8467 4402 5745 2861 6475 2189 2610 6892 7699 2208 7810 2449 8589 2389 6633 194 9182 5286 5642 7060 7257 1387 5153 1064 6688 170 2235 2664 7560 3726 9578 2167 5778 2495 6844 7302 9770 1322 6025 2828 8141 2277 2557 1227 7427 211 1943 7852 8326 4153 4700 6205 7095 3710 5421 3965 6859 490 6650 5334 6002 8981 9313 5722 9682 1731 5709 281 1648 1694 2182 3474 5645 6239 6469 3789 4386 3616 9782 8571 8707 4897 6635 574 5272 1177 2953 932 2737 2275 6392 1618 9601 1273 1504 2620 6642 1896 5754 4309 9064 153 5158 6869 8467 3752 9981 4399 6247 3752 9078 8482 8542 4765 6338 3511 8655 4358 8338 502 3750 6876 9434 871 5357 3791 5046 1506 8173 3902 3915 69 9045 5805 8322 1379 3585 4339 7049 8502 8838 443 1017 1122 3543 5286 9683 571 7000 7464 …
Output: 7944

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The registers at Glowfen - MEDIUM Coding Problem | CodeTikki