CT44466

The Link Budget of the Secret registers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the cinnabar mines of Vermilion as Scribe unrolls the day's manifest of registers. The tally will decide the next shipment. 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 1 2537 9364
Output: 9998

Example 2:

Input: 10000 1664 1098 1138 2879 5604 8130 9205 8483 9503 812 8008 5143 8168 1833 6993 5937 7482 2942 8385 130 2809 6605 7653 2528 3533 70 7054 3300 7706 2199 8762 148 906 243 3526 4493 5952 1330 1684 224 2601 2005 8807 3540 4023 1130 6124 4474 7623 27 1713 1423 6413 4757 7885 2584 9662 1795 6995 1991 7252 5283 6166 5159 6656 528 8180 294 7088 3234 8396 4702 9193 652 3880 4087 5485 5044 8990 2389 8850 8268 8946 356 527 1917 8605 1209 2178 631 8613 8646 9257 1738 1749 7053 7552 4489 5518 1981 7090 4175 7805 3756 6755 2165 8545 378 8221 132 5049 1469 6324 4015 5019 878 6734 240 7488 746 6364 4540 5084 2185 2535 38 7719 7990 8556 8792 8857 302 6260 2664 7134 6548 9990 10 44 1895 8357 723 7818 2430 8356 2244 2593 47 494 434 4154 6477 8649 6338 7755 3250 9099 2985 5588 5352 5495 4520 7840 2286 8719 33…
Output: 8335

Example 3:

Input: 4000 370 517 569 419 1857 434 2673 2315 2466 1984 2740 115 1110 650 1114 2296 3906 105 2718 539 3071 979 3668 1079 2430 2286 2333 792 3452 1712 2766 919 3553 481 1363 15 3519 3191 3419 3138 3879 2395 2975 92 3300 2518 3137 2739 3678 308 626 2371 2482 2173 2709 1394 2358 1494 3730 1651 2372 269 436 446 1846 1835 2661 3074 3322 851 2072 715 1931 266 1682 51 2903 448 624 826 1702 1000 3146 2540 3961 836 3630 451 1615 2379 2746 567 2288 1563 3630 3100 3879 518 3954 967 1428 459 1560 3194 3648 1156 3915 366 3202 199 2342 2585 3505 712 3266 861 2909 591 722 293 3290 573 1629 929 3751 1416 2719 2633 2923 2431 3649 1145 1193 178 906 1583 3851 290 1782 18 1500 1917 3104 1611 3878 1091 3460 287 805 2141 3521 77 2888 348 1140 345 3969 490 547 780 1737 1815 2519 208 484 2212 2684 195 1816 396 2994 275…
Output: 3629

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.