CT35276

Sailor's ledgers Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Sailor the tallyman watches over the lakeside town of Mirrormere's stores of ledgers. A careful computation stands between order and chaos. 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: 100 3725 21 93 51 61 32 59 34 57 24 93 13 87 2 25 39 100 38 92 8 49 12 90 75 86 34 42 45 81 15 70 26 89 4 57 6 95 23 83 9 84 79 87 52 95 12 62 3 21 7 91 25 32 21 39 24 36 23 85 38 52 6 63 50 74 30 72 27 85 65 75 1 45 31 36 30 87 14 30 14 54 4 63 48 57 78 85 20 88 51 98 39 84 63 87 16 33 19 54 41 71 17 21 2 44 62 88 2 32 57 88 48 83 40 83 47 67 27 97 20 46 9 12 14 73 31 77 39 51 13 35 8 56 19 92 69 93 5 74 28 55 4 74 59 90 29 80 37 75 12 41 17 38 64 83 41 43 67 86 18 50 13 99 8 17 16 40 53 65 36 79 43 72 88 96 45 52 37 91 22 100 12 98 11 15 41 95 30 48 76 93 58 97 49 59 74 100 49 76 34 67 25 29 22 23 5 50 24 86 44 87 18 67 51 65 48 52 30 68 12 46 74 80 61 72 12 27 3 32 10 20 32 60 36 59 38 79 42 50 9 42 87 99 35 37 74 87 3 34 40 77 37 73 13 64 64 77 3 33 52 90 58 60 48 91 79 94 45 57 4 72 6…
Output: 0

Example 2:

Input: 10000 23 72 3790 475 6753 4055 8405 852 6252 6409 9033 6059 7987 3015 5481 5592 8309 1803 2021 4369 7782 3585 8542 7043 8561 3571 4056 4560 9158 3843 9645 984 6253 570 969 7256 8592 1146 7346 4849 7863 3 863 393 3356 4560 4608
Output: 9976

Example 3:

Input: 4000 1209 1818 2981 1795 2315 1207 2937 648 1876 1367 1782 2929 3597 487 2437 132 2575 522 2969 1228 3765 1113 2606 1829 3705 444 2100 2920 3326 95 392 481 593 1519 3583 1068 1149 2439 2548 2695 3910 1975 3962 10 2581 1584 2888 1460 1745 963 1271 284 1228 1313 3224 84 3834 1689 3328 3502 3520 379 2079 1278 3177 2080 2222 1396 2179 1550 3923 553 2940 1837 2160 2197 3749 3100 3278 1041 2082 847 1007 3264 3357 2087 3486 216 666 1592 3642 350 2116 2880 3102 2022 2191 2263 2736 198 2547 1057 3026 1211 1253 1060 3631 621 1899 1607 3988 2346 3922 414 1117 2233 3020 1542 1639 20 1491 411 1944 286 3655 2153 2540 208 3031 71 952 1126 3638 1115 3020 329 877 461 747 190 304 56 1263 970 1122 1728 2190 2779 3268 901 1632 1143 3923 422 2188 1552 3019 2745 3012 2151 3712 571 3963 2227 2252 1389 2695 2509 …
Output: 2790

Constraints:

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

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