CT55785

Dev's Link Budget Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Dev the cartographer watches over the ink district of Scriptoria's stores of signals. 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: 4000 469 511 3167 2170 3980 1956 2273 721 3486 59 2083 2673 3638 2336 2470 1556 1585 578 2954 1221 3418 376 3897 1481 2708 2003 3165 2151 2341 1365 2192 114 3243 933 2722 1275 2771 685 3834 3708 3736 648 3237 2835 3431 1673 3239 3676 3722 620 1849 1577 2760 1386 3290 304 468 1147 1632 3887 3970 1638 1680 1768 1817 1650 3534 2107 2808 743 2950 109 1327 1706 2013 2070 2607 1861 2157 509 743 854 2365 1215 2187 1734 3954 1775 2992 226 522 1580 3681 1494 3321 2334 3201 1916 3611 223 279 389 2422 512 1492 2312 3876 2788 2834 1351 2038 680 1004 1692 3907 808 3615 1550 3841 963 2337 288 3098 148 1899 1567 3761 1398 3246 400 1719 2899 3806 3172 3635 876 1084 207 901 1363 2354 1962 2139 105 3216 3397 3413 927 1902 857 1687 851 1130 1005 1229 337 710 695 3197 1251 3706 435 3540 3056 3879 256 3080 172…
Output: 3530

Example 2:

Input: 4000 863 10 2400 1228 2480 428 3830 214 1042 197 2706 775 3983 472 2770 2150 2326 2289 2511 2433 3132 1926 2916 1664 1899 242 3960 33 1209 1164 2233 462 2743 134 1572 878 2266 384 503 1046 1381 591 2101 199 3110 970 3425 1159 3812 11 1642 1372 3612 2667 2692 852 2829 683 3047 1744 2118 3156 3270 1289 2520 2167 2381 3471 3733 1449 2045 1115 1674 1439 2238 2217 2869 3491 3831 223 1756 47 3848 1772 2133 180 3095 2388 3653 1693 2749 3254 3992 1902 3147 1221 1519 2887 3962 1779 2995 700 2768 1647 1951 1647 1974 435 531 1264 2809 1266 2688 2648 2650 427 1066 498 3732 643 3590 714 1024 408 3092 757 2769 1538 3645 856 2898 1271 2439 190 2065 982 2663 2814 3746 2271 2965 3664 3831 716 3183 900 2544 1356 2764 185 3122 1418 1861 1710 3705 2408 2419 855 1165 2811 3860 1438 1728 1314 3825 878 2344 773 …
Output: 3136

Example 3:

Input: 10 40 1 5 5 9 3 6 3 5 7 8 1 6 9 10 4 7 5 7 3 4 2 4 1 8 2 6 4 5 3 7 6 9 8 9 2 10 2 7 4 10 2 5 3 10 2 8 4 6 7 10 1 9 3 8 1 2 1 3 8 10 5 6 3 9 6 10 1 4 5 8 4 8 1 10 6 8 2 3 4 9
Output: 0

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Dev's Link Budget Ledger - MEDIUM Coding Problem | CodeTikki