CT46039

The Starlit beacons of Miller

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Miller found an old ledger of beacons in the mint attic at the ember dunes of Ashfall. The margin notes pose a precise question. 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 1776 50 57 31 47 14 70 48 50 43 86 71 82 65 83 67 99 26 77 19 94 6 52 39 92 7 46 22 57 9 38 11 49 63 83 27 31 88 98 17 45 31 42 12 22 63 75 22 68 22 63 30 78 17 87 21 77 34 45 40 80 21 61 15 31 5 37 32 88 30 62 51 72 50 56 9 75 23 89 3 82 88 94 19 81 6 66 54 60 34 68 19 42 37 89 79 84 33 71 66 80 40 58 59 97 31 83 12 83 1 5 23 27 51 100 61 90 91 100 19 61 74 81 17 35 66 99 77 94 80 81 53 85 24 50 4 39 3 81 48 51 15 30 36 76 29 61 1 82 44 59 34 90 84 91 8 89 52 91 34 78 4 57 25 85 94 99 77 93 79 85 35 89 3 79 59 75 23 90 74 98 48 49 2 78 63 69 32 96 78 79 32 68 3 27 65 88 79 81 1 23 43 47 10 98 1 58 35 44 74 86 70 95 18 33 50 78 14 74 43 83 52 58 34 67 36 61 4 12 32 67 5 52 5 73 27 63 30 45 48 79 4 48 1 43 62 100 58 93 67 73 65 100 80 98 11 95 22 47 57 72 16 21 52 97 45 89 19 52 1 59 45…
Output: 0

Example 2:

Input: 4000 952 780 2159 380 699 767 3891 3403 3605 378 3085 356 880 723 1165 1408 2680 1232 2404 1552 3595 2000 2206 526 2665 2333 3217 2964 3726 262 2744 77 3169 1754 2596 825 3703 312 1753 31 1487 832 1911 2122 2761 637 2178 3266 3320 86 2020 3000 3481 236 2520 192 3669 1873 2433 690 2044 1311 3806 1030 1699 354 1710 3641 3704 1966 3452 2202 3903 279 2617 1882 3129 1396 1541 895 1208 1645 2407 3169 3898 594 2330 2384 3777 1099 1457 255 3271 604 609 356 909 2960 3316 2139 2658 1016 2811 1722 3569 539 3758 1565 2921 1550 2344 1841 3583 976 1076 910 2211 950 1322 3919 3949 1274 3560 1316 3435 3084 3447 803 3762 1490 2698 701 3899 111 3886 1987 2579 554 2144 1769 3532 3601 3754 401 2508 336 3096 212 1465 104 3700 1631 3664 165 2469 532 1272 839 2000 2686 3152 680 1029 204 2481 1014 3879 2115 3023 …
Output: 3047

Example 3:

Input: 4000 2793 1277 1723 1332 1855 640 1443 670 730 2014 3594 3048 3641 1854 3210 188 1197 132 1376 2293 3487 510 1115 1358 3767 2492 2877 1684 2585 1988 3127 1228 3549 1320 2381 1785 3023 77 1126 855 3466 3424 3750 131 2361 913 3961 473 1112 860 3434 872 3937 299 3084 904 2231 3069 3566 1077 3910 1371 3063 128 2470 79 3553 2371 2538 396 2659 1495 2938 1284 2654 2 3752 374 756 184 1336 1702 3219 400 3507 1010 1503 555 2155 2744 3855 1416 2641 531 3912 1181 1244 2081 3955 134 2285 1538 2629 999 3348 530 816 1675 3641 403 3719 300 1916 1125 3661 1096 1551 211 2472 318 2265 598 2131 221 1340 590 1569 8 108 784 3729 1611 3941 110 2442 283 3400 2205 2494 525 1124 3677 3954 2789 3877 157 1054 215 2919 1214 2547 436 2927 894 3795 1493 2625 349 2856 869 2264 806 3911 1310 3744 17 348 2195 2714 2139 394…
Output: 1277

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Starlit beacons of Miller - MEDIUM Coding Problem | CodeTikki