CT56963

Ulric and the Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The bookkeeper Ulric has been asked to plan the harvest festival. On the desk lies a long table of marks readings. 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 3351 1433 9519 2076 7997 9284 9329 2286 3778 1002 4827 607 4553 4595 5984 2762 4614 1632 9373 2096 6780 8816 8958 3551 5498 6889 8611 1304 8466 1102 1506 4257 9606 5031 6685 2386 2998 559 5196 3023 7434 3342 7867 779 4416 3208 5414 6130 7711 7197 8118 118 8220 1963 2421 1537 3231 3949 6456 3524 3786 4219 7189 597 4341 1466 3420 338 6943 8130 8803 3162 9288 3129 8028 2440 4437 1385 2017 2971 4699 5083 6087 7474 8999 379 1214 4362 8026 6233 6537 1162 5521 1622 8178 7140 8482 7839 8805 5001 8420 6862 7799 1962 4657 4468 9480 4671 6712 1954 3815 2886 4757 3235 6674 5546 6471 2763 5308 2136 6503 7237 8449 2865 9898 4290 9728 3139 6453 6701 9281 830 2124 6715 6840 1050 8730 8269 8868 8031 9176 1628 5810 3078 7600 2313 2484 4266 9309 6396 6730 953 1011 7389 9704 2424 6379 1328 1691 1898 971…
Output: 6648

Example 2:

Input: 4000 592 914 1829 121 1774 13 294 1953 3650 2007 3951 1004 3502 659 1783 1266 3687 2196 3498 2772 3665 229 665 1028 3756 2107 2424 503 1554 436 1633 3221 3449 3378 3714 416 2910 10 718 3925 3933 1348 3572 57 630 696 3518 31 214 2917 2932 22 1900 1771 3514 424 3487 654 1448 834 2150 2735 3236 349 1894 24 1682 1277 1594 2150 2503 1362 2373 1357 3628 1020 3938 387 3252 2945 3516 532 1368 1087 2665 2196 2258 2199 2325 1318 2025 661 1626 1145 2481 1850 2715 680 2799 59 152 110 1508 125 2868 594 2253 1758 3603 962 3634 170 685 1905 3638 1026 1705 1856 3096 350 1158 626 2083 1321 2395 1012 1613 1120 3958 361 1874 2192 2319 115 931 1843 3190 584 2826 656 2907 3785 3980 1491 2589 2354 2762 576 3483 1787 3875 2340 3805 1901 3665 3150 3249 3297 3304 333 3417 1829 3672 2293 3710 3068 3422 19 898 989 1…
Output: 3407

Example 3:

Input: 100 3991 27 76 22 84 8 69 90 100 45 89 12 90 58 65 12 56 1 48 21 37 15 81 12 98 2 15 45 80 68 99 58 76 54 77 87 94 40 92 24 44 43 71 7 78 5 24 16 25 37 63 32 65 10 63 7 77 39 44 47 48 30 98 71 90 59 89 67 92 58 83 20 61 16 31 8 63 17 58 43 47 26 54 2 47 41 88 33 86 33 55 39 69 2 87 1 93 39 68 44 61 25 66 38 52 10 32 1 99 15 63 85 89 13 15 24 55 37 61 67 81 8 40 59 93 7 80 39 55 5 84 91 93 5 87 36 38 26 74 18 37 7 23 5 45 20 66 6 96 35 67 14 68 20 41 9 54 4 40 27 89 51 74 13 46 9 69 2 92 75 85 28 57 21 95 11 65 54 60 89 90 46 55 12 66 57 75 2 88 32 56 14 20 4 64 3 59 44 52 17 98 64 66 58 64 8 27 33 98 88 91 20 49 17 62 24 85 64 73 13 91 35 45 32 54 81 96 2 86 59 72 14 93 20 84 31 60 72 79 11 35 50 86 29 96 55 94 69 99 23 72 11 88 14 35 25 49 18 96 2 21 51 98 70 80 18 27 8 98 56 98 71 93 78 …
Output: 0

Constraints:

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

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