CT36505

Secret registers Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the salt flats of Palemere with crates of registers, and Notary the scribe must account for every last one. 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: 10 17 6 9 7 10 5 10 4 9 5 8 1 5 3 6 1 6 2 10 7 9 4 6 7 8 5 7 2 7 8 9 4 8 4 10
Output: 0

Example 2:

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

Example 3:

Input: 10000 3948 1389 9216 9727 9804 5179 9001 5682 9371 324 2435 4468 9010 1881 8098 4871 8410 2561 7031 1758 9837 110 6100 2838 4425 7227 8837 6400 9880 1529 7125 4373 4936 7484 8380 3154 5454 5304 6208 7 8162 620 3850 4853 9102 585 6088 4581 7776 1946 5240 6567 8430 7617 8045 3702 7679 4255 8839 113 172 5107 9660 758 7071 869 6900 3151 9469 711 1615 5144 8460 4135 9288 3211 5727 1635 5705 5956 9299 344 9683 1711 2729 3476 5383 339 3677 1802 4578 4246 5365 7293 8177 2778 8999 3433 5122 360 2795 2952 3444 1835 8423 3680 7783 5444 9285 6162 8954 499 5089 3089 7483 3019 8729 4336 7973 833 2098 6310 8081 2173 8351 629 1174 2415 6836 4074 7042 3085 4707 1935 8253 2772 5445 2888 3851 6565 9719 5606 8431 1048 1216 552 5612 4657 8446 6748 9766 1579 2796 791 5407 1514 1833 1463 7970 8811 9918 1263 2356…
Output: 6051

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Secret registers Link Budget - MEDIUM Coding Problem | CodeTikki