CT39361

The Link Budget of the Windward signals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the zephyr cliffs of Galeholm, someone must restore an old family record. This year the task falls to Baker, 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: 10000 1207 189 9355 1400 4506 1575 2879 1013 6216 4894 7721 409 580 8421 9043 2326 5954 2226 8928 2866 7897 636 5973 8117 9492 944 5235 6529 9001 1505 9411 2123 2340 3110 6134 4961 6724 2928 3129 2215 7177 569 3415 1111 3368 366 2793 371 9802 2199 8623 4322 5353 2006 2976 5956 8615 4566 6463 2123 8596 767 3998 5842 7265 2880 8729 497 6229 5506 9451 98 3670 3900 7354 2859 6335 1552 9574 429 6713 5324 8490 1525 8152 584 6005 895 5928 653 7240 5113 8623 4433 9173 3112 4441 2917 4183 108 2126 6066 7237 3043 3256 5773 7618 3914 7126 373 2329 2135 7582 6960 8534 2911 7546 5145 9140 5750 7266 4527 9999 5597 9788 7153 7318 2515 2589 4830 9227 4256 5988 1465 5589 1910 4336 74 3300 3174 4400 2393 7085 1424 9226 5782 6218 4832 5132 441 2061 4325 9383 628 1346 5344 6603 573 8913 3623 6918 21 9326 1892…
Output: 8792

Example 2:

Input: 10000 1983 391 3882 5719 8356 3987 6724 94 5719 2014 7632 1349 4108 662 9898 3245 5034 5772 7531 151 7653 1437 5442 2930 2969 507 2752 8397 8635 4776 6043 3410 5421 5526 9187 5926 5976 5339 6946 39 6110 2957 4328 1470 5299 323 5628 273 4346 3218 9319 4552 7863 5566 8716 2594 9327 1528 6067 1369 9411 1198 4600 4626 9507 3399 6531 307 2835 1196 5530 4058 7441 3474 4857 2733 7629 4409 6260 2007 7834 89 5926 4106 6216 5465 8776 228 538 994 7935 1809 4757 2315 2647 4048 4287 1537 8636 3847 6638 4712 6558 406 5213 2131 5520 2391 4985 4947 7852 4484 5047 4882 6261 1688 6898 5927 6696 933 6004 650 9552 1257 5729 5381 9615 1180 4429 2506 3183 2304 9097 2358 9804 4727 6432 3492 5248 2036 9979 6486 8555 4757 6363 3634 3731 7148 7793 7467 8679 4229 7157 1782 7869 3933 7611 2085 2588 6508 7553 3665 505…
Output: 8016

Example 3:

Input: 10000 2781 17 8966 3461 8121 1262 3778 9031 9502 7767 8421 2250 8796 7264 7763 4002 5050 3975 9612 2490 8909 8007 9529 4098 6138 5848 7761 2647 5416 4267 4693 2155 7377 5923 8450 1428 2368 2455 6753 7026 8777 218 5398 1865 4966 4425 8990 747 8053 5772 6148 519 9062 1964 6607 3109 5430 5284 8677 1961 3586 1145 9687 292 5402 3209 8682 365 1196 2851 2997 8036 9607 2214 6979 6633 8182 740 5765 4490 9661 781 1760 1508 8144 8700 8800 5819 8517 1771 8516 2434 7914 5662 9174 4472 7195 1654 6370 2557 8722 718 4063 1433 8699 5871 8038 58 9988 1447 3777 988 3780 146 3769 4674 9806 7120 9736 4749 8307 5334 7496 4596 9119 4749 6025 1462 9067 4533 4595 2526 9291 2354 7046 2964 5714 12 5780 1956 2936 1759 6005 2286 7943 1893 9270 855 8956 5446 8952 4400 8867 1897 4146 3810 5466 8625 9426 4448 5921 4516 7…
Output: 7218

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Link Budget of the Windward signals - MEDIUM Coding Problem | CodeTikki