CT36906

Marek's Garnet beacons

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the eel marshes of Slitherwick pays by the answer, and Marek intends to earn it. First: the full register of beacons. 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 170 14 94 77 88 63 83 75 86 8 78 17 46 53 82 28 37 57 82 44 55 54 81 12 39 92 100 37 83 12 38 32 52 18 24 35 61 12 47 67 72 36 97 8 89 22 88 14 59 58 99 58 66 47 83 41 45 35 86 64 92 4 54 86 90 26 89 47 48 14 90 23 89 13 45 19 63 21 79 40 64 50 84 12 20 7 86 6 84 34 87 49 90 8 44 54 95 64 79 41 66 32 95 27 64 78 86 49 73 18 57 32 96 57 68 22 52 67 69 44 62 29 41 44 92 16 94 70 84 2 28 11 87 9 67 29 61 9 75 81 85 23 77 25 26 19 46 30 41 36 71 6 45 37 62 5 91 28 75 42 73 14 52 29 80 26 56 2 10 14 73 11 80 18 75 21 53 35 84 49 83 22 28 62 68 51 85 21 43 54 65 15 56 42 48 73 88 7 17 44 82 13 72 3 57 24 67 29 38 54 80 10 25 10 79 58 85 93 94 16 43 36 68 16 55 27 85 83 85 27 48 19 73 2 21 8 47 56 60 46 100 81 89 55 91 2 6 23 51 64 99 3 36 5 81 48 91 53 71 9 57 92 95 31 48 51 71 77 78 1 18 59…
Output: 2

Example 2:

Input: 4000 3372 2602 3542 25 2690 1533 2470 1818 1992 678 1262 3420 3582 3408 3628 1443 3274 33 834 3409 3515 248 1678 717 2094 250 3588 444 951 2296 2893 581 1850 304 2231 1715 2001 252 313 1230 3790 696 2790 861 3087 3756 3965 1395 2390 613 3474 3093 3494 616 1476 430 2812 1140 2905 1170 2227 1877 3635 1308 2173 2951 3479 2703 3220 617 3468 1244 3505 2107 2396 903 1122 1291 2435 518 2769 1766 3708 921 1491 2051 3062 3019 3108 1390 3151 91 3059 1305 3779 209 2723 1393 3771 568 1717 1663 2871 2062 3045 2814 3574 1682 1740 201 3821 1312 2818 397 3236 2838 2878 253 485 95 2030 104 2729 166 460 2141 3774 1236 1917 1167 2333 2220 3405 590 3210 3153 3263 636 1503 795 2336 70 494 263 2259 355 2464 462 3312 2721 2808 855 3255 1771 3877 2883 3974 1022 1450 1056 1157 1548 2498 1894 3151 105 3378 401 2802…
Output: 907

Example 3:

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

Constraints:

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

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