CT55566

The Applerun Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Minstrel inherited the kitchen at the orchard lands of Applerun 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: 4000 2727 421 1375 835 2726 2433 3896 1363 2787 206 3321 621 3916 823 3674 1353 3308 1020 3693 2199 2682 2487 3747 241 871 476 1297 325 2589 2418 2739 1560 1609 3226 3586 3274 3885 1084 1656 610 1330 2700 2861 1345 2202 321 3768 1596 2604 1223 2166 656 3241 788 969 2192 2540 1461 2955 253 3911 192 1896 1565 2684 709 1413 2177 2711 1606 2474 679 3945 1580 3078 1329 3781 692 1676 1784 3891 1575 2424 238 1253 1359 2809 346 2372 928 2044 930 2482 780 3534 540 1078 2138 3564 956 3518 1279 3248 947 3901 555 2115 862 1447 1664 3384 1691 2742 3683 3809 2122 3962 1393 1468 696 2322 2699 3309 1154 3681 2187 3310 1500 3471 3178 3339 1171 2370 787 3453 2461 3629 1590 3841 1502 3288 2368 2418 31 98 257 2467 646 2424 1978 2457 2580 3849 2418 2816 2238 2472 1244 3267 2455 3352 2163 3981 1790 2922 2006 31…
Output: 1344

Example 2:

Input: 100 82 14 93 16 83 56 80 49 64 22 50 54 72 64 66 56 91 89 96 27 83 46 72 18 56 49 93 15 95 58 74 41 97 11 62 31 53 55 83 54 74 40 70 23 96 79 88 77 88 43 56 65 70 59 72 52 73 65 90 16 71 29 78 16 36 68 76 9 82 42 71 27 96 74 84 2 90 31 59 16 64 14 54 3 77 22 84 23 41 59 88 36 88 83 96 30 55 95 98 77 98 36 62 61 63 24 33 73 76 16 39 55 59 84 99 50 64 52 90 8 80 51 70 80 85 2 23 64 90 63 91 35 74 25 70 47 50 46 63 33 98 36 98 9 11 15 29 71 100 10 99 76 86 17 74 62 85 41 76 26 75 41 53 81 91
Output: 26

Example 3:

Input: 10000 3015 1461 2588 4108 7724 6725 9709 6688 9430 1967 2035 3722 5974 2331 7454 5764 7831 2153 3388 85 4914 761 8609 45 6127 2120 7528 3009 8208 4545 7609 4571 8783 418 1885 748 2077 5378 5779 5099 9988 3208 6157 3919 6227 7842 9605 2109 7863 2219 9493 8863 9128 6684 6689 5405 6404 7872 9891 1239 3416 204 2728 209 3571 454 7048 1636 4510 6785 9951 1948 8147 2231 8340 675 9450 2748 9367 6492 6603 2318 5769 1251 2223 8458 8611 6225 8453 515 9418 7339 8600 4343 6107 3715 8292 2253 2879 3716 6620 5895 7594 6008 9335 2899 8834 405 7551 1676 8482 3092 3846 6986 7768 7637 7818 2185 5881 432 2500 2038 9586 2814 8933 1468 4239 2581 3741 3763 9461 2998 6094 1129 6020 1819 7811 866 1225 2859 4493 34 6852 1793 4507 1762 5197 4237 7245 7242 8907 1961 5874 5832 8018 3320 9154 7693 8335 8865 9135 3143 5…
Output: 6984

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Applerun Link Budget - MEDIUM Coding Problem | CodeTikki