CT52615

The Link Budget of the Ashen ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the crystal caves of Luminar, Maya records each ledgers in a worn leather ledger. The guild wants answers, not guesses. 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 3457 2266 3129 2136 3761 2076 3479 2338 2751 2931 3901 1759 2356 1198 1393 1112 3347 1961 2789 1671 2058 788 3594 2344 3284 1052 2251 660 1719 1627 3897 23 325 1816 3828 80 182 1077 1264 719 1477 512 979 2760 3074 21 3684 1573 2839 933 2154 1829 1916 2119 2561 435 3654 525 3227 659 2970 1580 3968 89 1809 2041 3037 280 2774 858 3996 1046 3887 1768 2706 937 2009 878 1998 787 1550 748 1215 2912 2952 404 2964 2438 3426 661 3895 895 959 3600 3643 284 2620 113 2549 562 2789 252 3837 803 2475 1053 3528 2752 2892 1215 2152 1201 1276 10 1964 2236 3260 175 2901 377 1248 3215 3779 297 2521 1557 1748 414 2604 76 1787 1399 3640 2166 2543 2194 3697 1823 2132 915 1017 2379 2544 508 698 1069 1162 2223 2424 1305 2293 839 3698 340 2735 412 3125 809 914 857 2464 5 2781 796 3321 44 3375 2968 3773 84 131 …
Output: 888

Example 2:

Input: 2 0
Output: 1

Example 3:

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

Constraints:

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

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