CT44497

Ulmar's Crystal signals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the opal reefs of Shimmerdeep, Ulmar the auditor keeps careful count of the signals. Schedule the next expedition, every figure matters. 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 1816 4730 5555 516 3083 8141 8546 7816 9302 3153 3592 7955 9247 2182 3246 2033 3882 1206 9692 2102 6766 967 9955 3824 4872 6792 7787 746 6982 8804 9687 1972 8875 923 3537 3214 6866 4488 6445 4466 6484 1398 7596 2146 6261 1838 9234 177 7635 1640 8669 351 6543 75 5751 5441 6995 3192 4484 6031 7234 1618 3546 4630 8109 262 5595 199 5065 3444 4887 1246 7046 9247 9786 6019 6745 2180 3035 1500 2611 3747 4540 2065 2408 6444 9672 1259 2069 2267 8164 2526 5169 6641 9572 444 7628 5355 6376 5111 7891 7506 7985 1753 8741 2159 6126 5084 7778 676 3894 98 4125 5558 9518 6993 8154 79 899 343 3380 1471 5509 3548 4002 8858 9631 997 4972 4888 6877 488 9940 2479 5529 948 9378 5754 9138 565 8898 23 6834 1379 9529 2680 4046 2269 4173 5653 7572 1444 8367 712 1181 980 7524 699 2028 702 942 419 1067 3325 9246…
Output: 8183

Example 2:

Input: 4000 3448 1094 3333 200 2993 995 1898 838 1368 1966 2231 1993 3402 302 763 1336 2318 269 2065 1335 3913 952 2241 787 1905 371 385 1528 3279 266 629 23 3218 1923 2480 1680 1977 211 798 2051 3833 352 485 1851 2947 573 2248 777 2879 654 1102 466 1173 2908 3876 17 160 493 2898 28 509 262 715 3387 3680 1409 3692 1581 3957 543 2214 1376 3115 1320 3933 3318 3921 2160 3021 372 3442 1457 2185 1052 1390 603 3469 1672 3615 248 380 1698 2740 2520 3638 2779 3000 2281 3223 261 3667 2633 2780 1177 3173 3514 3606 3281 3403 1281 2887 736 901 246 1575 1006 2225 1606 3975 274 3199 402 2740 340 376 1049 3082 1272 3800 928 2153 115 1469 354 3973 2091 2662 3873 3905 3046 3059 444 1379 490 3780 3150 3173 353 1476 332 2937 517 1240 2368 3641 3184 3395 2630 3639 2304 2835 1034 2931 1221 3139 2579 3544 1059 1553 17…
Output: 886

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Ulmar's Crystal signals - MEDIUM Coding Problem | CodeTikki