CT42120

The Link Budget of Tuskmore

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the boar woods of Tuskmore; Zara weighs the day's beacons manifests and starts the calculations. 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: 100 2815 6 65 33 96 17 35 51 95 14 76 91 97 9 75 26 58 75 88 53 68 85 88 48 74 66 72 4 8 23 41 21 43 39 98 8 15 42 72 22 80 82 90 6 48 20 85 3 5 28 91 23 76 73 85 21 25 34 64 10 12 72 77 33 39 4 19 24 81 22 28 57 72 28 84 40 87 64 96 68 87 14 55 56 58 14 59 3 22 17 18 50 94 5 30 40 98 54 68 1 38 38 41 71 87 25 37 43 55 22 39 64 93 78 86 13 67 11 22 55 94 75 82 63 85 69 72 53 92 67 86 12 95 47 75 8 66 49 90 5 82 80 98 2 19 91 96 16 59 3 36 27 59 64 71 25 34 79 93 54 92 66 93 57 60 66 95 71 85 9 47 8 54 50 87 33 77 20 28 8 35 9 45 11 77 49 97 57 79 5 97 14 92 6 90 7 62 24 99 33 80 28 79 57 80 23 74 1 13 69 81 1 12 12 51 27 68 76 89 17 56 14 22 63 65 31 81 16 98 10 42 85 89 79 84 6 20 13 62 53 58 12 31 25 70 20 67 39 78 28 40 81 97 7 15 38 75 58 84 73 93 17 94 92 95 19 54 18 99 39 80 66 84 90…
Output: 0

Example 2:

Input: 2 1 1 2
Output: 0

Example 3:

Input: 4000 3945 828 1898 1825 2083 1376 2606 420 2605 1581 3584 735 2243 328 3110 1744 2394 745 1453 3011 3468 2501 2675 588 716 298 1115 1025 3428 992 2492 1460 2100 2103 3341 1049 1639 450 2037 2284 3931 397 2433 1469 1680 925 2283 315 1082 981 1231 1823 3286 1419 2943 1803 3342 1277 2686 2404 2561 2679 3746 3250 3995 160 2453 183 1081 1834 3350 758 3293 2201 2684 1525 3590 547 3441 118 1870 2053 2486 366 1928 138 267 57 2448 1782 2565 2487 3817 1226 1883 1463 2010 1088 2504 687 2680 1681 1822 377 3990 1816 2380 1458 3570 1165 3341 3291 3616 1354 2617 377 648 411 1556 1662 2272 360 2097 2341 3348 2867 3267 2123 2856 835 3143 1921 3189 112 694 2710 2728 231 890 1102 2978 3110 3168 382 3805 651 3649 1812 2227 648 2590 1382 2192 624 2822 253 3984 1222 3339 968 2573 2073 2447 2690 2821 388 1507 80…
Output: 660

Constraints:

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

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