CT45042

The Longlegs Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the heron rookery of Longlegs with crates of ledgers, and Zara the store warden must account for every last one. 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 1055 7183 7508 2958 3829 497 1366 4826 8750 1649 1836 5168 7881 5081 6610 87 5104 3217 9143 2194 7779 6164 9750 753 3315 895 8693 4455 7325 1095 2196 1681 1829 263 9516 7267 8383 868 1987 2830 7571 5708 8739 298 7809 1404 5232 4779 5649 9392 9996 1643 9512 141 7603 300 1240 2399 2888 1522 2337 5928 8668 2779 3593 2859 6663 428 7702 7440 8439 4950 6973 4199 9503 3432 7892 3096 4176 6614 6628 7288 9833 5860 5997 6261 6952 2381 7706 5901 7306 795 9944 25 2592 599 2179 396 8446 4712 7035 3253 7061 2246 5219 1003 8623 2884 4189 77 7858 4962 7014 1469 2122 883 8352 1530 4211 3246 4425 8908 9636 7074 8987 2434 3694 7635 8439 1669 9072 3689 3759 400 2575 361 1746 2661 6645 365 700 3273 4323 1771 5729 4095 8232 222 640 7813 9770 6559 9997 4292 5229 1171 1217 2367 8753 1940 9774 2277 3157 917 …
Output: 8944

Example 2:

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

Example 3:

Input: 4000 1730 1563 1597 469 1454 510 2464 786 2972 302 3830 3207 3679 2254 3515 1373 3835 802 2583 1947 3045 1386 1409 1865 3201 1824 3007 1590 2274 159 3498 805 3464 1166 3140 745 1182 483 738 1179 1238 211 3622 565 3162 2169 3755 1641 2281 3140 3791 557 2428 1346 3685 2325 3623 1347 2697 2644 3395 2544 3952 85 2404 1455 1880 1177 2171 499 823 2906 3308 3311 3441 2088 3604 471 1589 535 2192 1439 1760 1814 1991 2267 3406 287 1928 2926 3501 1948 2859 640 855 577 3581 717 2324 2498 3952 844 1755 101 2618 818 2132 1389 2337 1226 3097 825 1369 449 1703 797 2520 501 1381 474 3259 457 1807 714 2180 1578 2583 2357 2783 1252 1815 822 1767 1023 3407 2389 3638 249 1823 3349 3433 422 512 1161 2928 426 2257 213 2452 2124 3166 717 3172 1362 2424 1019 1504 1263 2937 116 905 3272 3305 411 3117 3077 3559 758 …
Output: 2269

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Longlegs Link Budget - MEDIUM Coding Problem | CodeTikki