CT57014

Nila's Moonlit Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The registry keeper Nila has been asked to balance the workshop's books. On the desk lies a long table of registers readings. 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: 2 1 1 2
Output: 0

Example 2:

Input: 4000 3245 1637 2413 1406 2325 2631 3016 296 1752 1484 3358 811 3172 3547 3825 1596 2191 184 2206 547 3003 1398 1916 1203 2649 1402 2671 888 1688 1181 2148 371 703 90 3938 2633 3842 1746 2116 605 826 1222 3260 2053 2326 1782 3291 2330 3165 2876 3165 126 3784 705 824 1460 1776 699 2841 1751 3459 1912 2787 1057 1490 1148 2047 1083 3049 1811 3253 730 1018 1656 3410 2269 3790 650 3645 426 1318 618 2322 761 1059 2327 3491 1308 2794 41 3427 561 580 3295 3319 29 516 2628 2910 1267 2798 2409 3801 732 3626 313 3798 747 996 2456 3418 326 1464 916 2181 771 2270 588 3120 2706 2714 1224 2335 2575 2749 2728 3005 636 692 207 2591 3815 3943 1289 1801 837 3565 379 425 555 3549 1313 3957 3306 3812 1860 3089 2281 3965 322 1670 629 3000 598 3754 1681 2733 2462 3543 3232 3395 1038 1934 1138 2570 960 3956 1545 3…
Output: 964

Example 3:

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

Constraints:

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

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