CT41662

Baker and the Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the bamboo terraces of Verdantstep; Baker weighs the day's beacons manifests and starts the calculations. 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 3065 2790 6666 1494 5342 5326 9741 8631 9640 593 7551 492 7523 2462 8487 2018 2401 1985 7140 7100 8127 2093 4640 9338 9741 1287 6148 3393 4998 4235 7329 2415 6017 8796 9509 5934 8425 3676 6566 3500 6051 6419 7689 3255 7297 6181 6846 7884 9461 850 2351 7787 8151 2763 5048 2763 8174 373 8281 900 8348 7867 9805 3493 4599 4354 4678 2925 9405 1503 6734 5059 9493 7620 8869 4541 8392 1426 9916 431 1209 2334 9723 201 2042 4849 7471 6872 8879 2042 9381 4807 8865 1910 7400 1914 9636 762 2486 1068 3854 1190 6587 8176 9543 5713 8426 5259 9636 974 4163 3296 8612 1515 9294 1025 8669 6651 9686 2870 7215 386 8660 286 6578 5374 9703 3452 7183 2215 8477 7051 9184 7737 9727 8477 8785 2284 6867 2555 8563 3674 6638 2225 7882 5134 7095 6766 8213 2740 5314 1480 9994 6761 8696 6379 9114 4780 9274 1356 5502 …
Output: 6934

Example 2:

Input: 4000 3298 1915 3570 2349 3838 2036 2197 1558 3623 130 694 102 3322 1576 3786 1769 1844 1284 2910 205 3640 2193 2550 1781 2259 1539 3091 3014 3635 1895 2391 3311 3937 2594 2976 753 1069 76 1059 827 3945 713 2695 758 1997 645 2371 1656 2320 1496 3572 788 3227 1318 1586 2488 2580 3255 3790 3079 3370 329 445 1987 3550 2494 3079 3594 3724 2453 2581 1288 1394 646 3870 1913 2646 274 3289 1213 1406 2979 3712 284 1610 264 2661 1060 2818 3623 3850 1334 3164 2148 3692 1458 3435 1707 2039 1647 3381 1884 3560 298 2905 3525 3680 219 3500 581 1603 402 2316 1394 3462 506 1971 404 578 1802 2339 1256 1280 319 3825 410 3937 1063 3714 1481 3803 1941 3845 3785 4000 891 3393 1069 3508 559 897 1698 2234 249 286 2319 3300 2234 3932 2293 2789 1398 2273 1290 3583 3614 3964 1759 3616 674 2408 1524 2015 1545 2618 138…
Output: 958

Example 3:

Input: 4000 773 2832 3078 155 3564 466 2970 1795 2852 1531 3078 625 2607 85 1961 123 746 185 548 1200 3413 54 3075 217 300 771 3321 2991 3299 995 1531 809 3991 2729 3162 1879 2510 2016 2247 193 1568 2187 3218 1853 1951 1712 2066 309 3236 584 1952 2848 3592 2452 3061 408 600 1424 3433 489 2071 2086 2599 1568 2169 2158 3993 821 2960 1400 2717 113 1835 1524 2548 140 1630 273 3827 1685 2549 1997 3168 1651 1708 2080 3147 429 3624 2241 3688 2682 3067 2031 2374 221 2611 1025 3651 554 1846 1651 3462 1125 3787 669 903 1417 1848 860 3355 476 2642 548 3000 2497 2958 3486 3795 1669 2568 392 1296 840 2993 2461 3305 1962 3865 1525 2586 2357 3357 2488 3491 368 2938 378 1413 1144 3417 2427 3642 670 2158 1468 2950 972 2720 1800 2719 293 393 553 1881 1118 1941 570 3100 1479 2864 232 2297 1648 1763 170 684 1554 257…
Output: 3226

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Baker and the Link Budget - MEDIUM Coding Problem | CodeTikki