CT42737

The Caravanrest Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the dune sea of Caravanrest, someone must plan the harvest festival. This year the task falls to Varun, 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: 4000 854 2069 3808 2903 3620 1303 2967 3587 3841 317 3362 2401 3887 1142 1344 270 3585 199 2180 2177 3838 718 1744 368 1884 2393 3620 3448 3782 2675 2810 1031 3120 2433 3446 756 2347 986 1205 723 3677 619 3217 2237 2858 3764 3887 1222 2940 1000 3438 983 3803 2436 3760 759 2895 634 2347 1068 1789 618 1890 657 1695 213 3658 540 3480 17 2617 811 1518 179 1694 2702 3645 3340 3584 2388 2658 2259 3559 1101 2301 1675 3636 3294 3755 81 592 185 2564 859 1749 2915 3686 455 2791 681 2633 1466 2595 871 1998 348 3083 438 2983 3394 3673 20 1858 3061 3503 1098 3993 1786 3854 568 2084 1275 3740 736 2882 1405 1896 2982 3246 594 2800 913 1742 1193 1300 1011 3533 3552 3990 53 2274 1696 2951 834 2552 980 2176 2176 3428 394 3984 412 3687 3132 3334 1850 3804 941 2794 2973 3651 852 2661 3254 3876 2415 2970 6 247…
Output: 3145

Example 2:

Input: 10000 3325 1360 6034 2890 7417 373 2254 7334 9763 3799 7741 4232 6187 2574 7517 978 9053 605 6817 1157 6169 265 6816 3802 8776 4848 7919 1088 9453 3581 6034 7706 7759 3258 7524 4720 8521 3013 3184 5968 9267 2118 6085 3327 3702 2927 3551 420 2851 4722 8682 3939 8568 312 5723 3800 5998 4777 9562 870 4894 3381 6943 6464 8939 3133 4987 7106 7184 5168 5726 566 3151 3064 7037 7438 7863 2516 3999 5773 7024 1383 2594 3755 6745 3696 7266 4904 7083 3538 7485 5601 8154 248 5658 969 5184 4082 5514 4173 5786 1492 6784 4123 9903 397 3357 2895 5223 4000 9266 8890 9373 489 8769 199 1787 1737 5807 3473 9875 4532 9940 1082 7205 3298 6071 183 5137 1924 9336 6186 7760 1188 6871 1357 7935 1654 5123 2845 8949 6557 8400 2230 4881 5625 5815 2507 2605 3932 7413 8005 9138 3503 5835 1919 2062 2782 7984 1397 3362 185…
Output: 6674

Example 3:

Input: 10000 1526 4168 5481 1476 8393 2798 3310 1955 7220 2963 6135 1274 3390 5880 5945 1344 1386 5245 7948 7645 8416 7018 8241 1311 6762 2712 3096 5357 9178 3213 5950 2201 9035 4491 6830 1737 5195 2788 5068 1219 2895 6396 9015 883 4924 1922 7111 4601 6726 7432 8582 213 547 7486 8730 5065 7452 5373 9649 6365 6515 5636 9697 4251 7797 1911 8723 2418 5856 3816 4958 2980 9497 3810 9171 5179 6704 4371 7346 1658 9400 2469 3689 215 4133 3226 7126 5039 5774 4175 8934 3118 3313 632 5804 7286 9367 421 9321 1560 9522 41 752 177 5803 1807 5137 3150 4648 1267 3950 2439 6035 391 5827 2091 7446 1579 2715 337 4153 6121 9400 1266 2207 2193 4223 4158 7485 1002 4087 2373 5986 9025 9754 3774 6258 2818 7915 9630 9917 3566 4956 4731 8226 795 8158 1583 2228 1234 4491 2077 9965 1423 7660 3139 4496 968 4558 7299 7817 238…
Output: 8473

Constraints:

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

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