CT47000

Last beacons of Tailor

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Tailor inherited the loft at the eel marshes of Slitherwick along with its curious bookkeeping system for beacons. Time to make sense of it. 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 3636 3037 4429 1986 4556 50 3060 3211 9133 3913 6571 4736 7984 4210 8287 1033 9451 1016 1877 5246 8391 1173 1860 9663 9947 738 876 3033 5631 1811 2174 1024 2129 3899 7673 5140 6766 646 4255 1763 5524 178 3454 1708 4817 993 3282 2530 8854 7440 8598 5162 9517 162 2221 3763 8198 6378 8123 3427 4069 1565 4522 515 635 1130 9077 3798 4223 5926 8932 1958 8464 4528 9311 2069 4929 2198 8834 3109 6911 3554 4858 793 4124 1 7443 1934 6470 1958 5272 420 6759 2597 9426 559 9856 1826 4683 2639 9859 329 7703 1355 6558 1582 1635 1331 2374 537 2555 5692 7545 8513 9411 5599 9064 2712 7628 7945 9648 3150 5129 906 2405 7461 8508 1211 8737 1107 2614 2846 6488 3211 8741 289 700 433 3291 2045 3790 1170 8282 685 2498 2554 7755 3925 7058 3382 7033 1887 9865 5227 9223 3527 8609 5686 8725 6429 8735 4538 4601 54…
Output: 6363

Example 2:

Input: 10 0
Output: 9

Example 3:

Input: 10000 2591 2177 2215 609 3551 4426 5666 2748 5232 5537 8318 5672 9413 5068 9628 1508 2909 826 2793 1847 4177 51 8054 1549 7462 3407 6366 784 1744 405 8319 2150 2730 727 2798 229 7802 431 1227 962 6744 5302 5818 4412 6647 1335 5682 2055 2913 2336 7020 4358 9653 1414 8527 634 1492 7549 9992 3396 7029 817 3804 6476 7867 1204 7603 596 8862 2491 7173 169 8792 6020 6448 1597 7192 7111 7682 1221 4884 67 3141 3253 7309 885 5476 2244 4776 3899 8004 5183 6241 931 5379 3748 7297 2006 5710 6576 7353 7073 7830 219 4570 6460 9692 4584 8256 1991 3072 219 7032 3265 4920 5748 8479 265 8664 5202 7158 3647 9520 2290 7018 3625 6222 3236 9447 2102 8728 2922 4410 1108 5762 149 2836 4865 9038 490 7192 301 8956 490 4462 4685 8760 1763 6961 9409 9688 3901 5368 4833 6903 3797 4278 4763 5333 1534 2099 1426 2171 399 …
Output: 7408

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last beacons of Tailor - MEDIUM Coding Problem | CodeTikki