CT46284

The Link Budget of Glowtide

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the lantern reef of Glowtide; Silas 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: 4000 1105 1447 2579 715 2080 854 2973 2631 2907 299 3129 2033 3753 1293 1912 1379 1684 2270 2797 709 1127 834 3310 1605 2759 3298 3398 2844 3823 447 495 1774 2556 452 759 2219 2732 2656 3981 1701 3019 409 3547 565 2316 3137 3297 865 2393 598 2431 475 1806 1379 2096 1017 2793 1158 2223 2481 2823 967 2891 507 933 1145 3332 1122 2910 153 1554 57 1385 2599 3470 3243 3976 738 3100 806 3621 1637 3755 3362 3719 1042 3376 2236 2405 987 1378 1039 1351 926 3807 254 1477 229 3625 1185 2053 130 2177 3034 3943 404 1295 2374 3444 870 3872 2752 3364 420 1376 808 869 1243 3873 1995 2436 1397 2821 2799 3969 2734 3490 639 1856 962 3458 1357 2606 928 2077 150 3966 621 1969 2765 3835 1412 3227 528 3278 260 3804 905 3398 2201 3944 1659 2774 950 1145 918 2699 3236 3394 3393 3428 490 2008 332 654 2696 3452 1167 …
Output: 2894

Example 2:

Input: 100 2499 6 38 14 47 9 23 10 83 2 31 68 86 33 39 7 75 8 81 19 63 64 74 54 68 31 32 10 13 55 62 10 48 4 19 28 86 75 82 87 95 15 73 49 52 64 71 73 89 60 83 53 97 1 34 23 47 80 89 1 23 6 36 30 45 37 91 18 26 18 36 17 42 23 41 51 56 41 80 50 71 16 21 48 75 2 47 22 78 29 96 4 60 1 49 23 54 33 45 27 60 6 42 21 55 52 95 5 37 67 97 58 59 35 70 32 59 56 92 1 2 13 60 18 60 2 70 7 22 34 49 1 3 38 59 49 61 28 89 39 71 11 86 8 99 8 72 34 69 1 58 66 74 8 96 23 59 45 46 84 99 45 82 17 87 29 72 30 76 5 46 43 74 9 36 52 86 42 60 39 89 17 75 28 79 39 63 94 99 12 15 78 98 27 57 10 78 54 58 2 7 33 91 2 85 16 68 7 42 23 84 6 22 46 69 90 99 32 98 98 99 17 57 63 81 51 80 31 50 28 31 25 63 21 58 78 81 12 94 37 89 59 100 35 73 31 57 24 48 18 50 5 8 43 45 27 81 7 56 22 34 44 83 81 91 4 72 48 78 16 73 56 90 43 63 13 …
Output: 0

Example 3:

Input: 100 3211 38 99 7 75 50 69 84 93 15 50 13 59 61 98 9 70 48 99 31 59 48 85 50 74 24 85 36 44 62 86 36 42 49 91 67 80 3 35 62 70 32 90 60 100 63 81 7 62 67 99 26 31 72 88 39 41 48 97 24 78 39 77 41 52 24 71 39 63 35 89 66 79 11 76 79 96 10 30 79 85 28 33 81 89 39 57 34 67 56 72 41 87 59 90 45 79 24 42 2 5 86 94 59 100 21 70 36 79 32 72 4 51 58 61 18 21 74 94 24 30 9 63 12 98 23 96 55 92 7 86 85 91 86 97 32 91 30 36 44 45 20 54 15 53 49 64 1 4 80 88 42 78 36 90 41 96 2 93 40 53 30 96 95 98 60 69 17 56 30 86 30 97 60 71 29 63 18 93 30 49 51 95 21 99 44 47 27 100 43 88 4 67 80 84 14 53 13 34 73 84 41 43 23 92 7 78 19 43 24 32 60 75 61 94 1 33 11 49 15 59 28 87 86 99 6 29 26 93 35 71 20 39 43 82 3 30 37 83 20 46 42 47 3 63 70 98 3 12 82 91 45 89 5 21 9 67 68 72 5 86 21 25 35 57 71 95 65 93 29 52 …
Output: 0

Constraints:

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

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