CT47883

Petra Counts the ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the tundra station of Whitesnow, Petra studies rows of ledgers entries. One clean number will settle the guild's oldest argument. 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 1 8 10
Output: 8

Example 2:

Input: 10000 2376 24 8482 7 76 3996 6124 1752 7530 7413 7484 7150 7481 1169 7954 8447 9016 4267 6621 4094 5271 3159 8161 1376 5990 1563 3916 264 4656 3022 8072 4160 8719 6830 8346 6954 9210 1357 3149 4293 8019 5053 6482 795 5392 5067 7258 4907 8354 3239 5384 1185 2781 2499 6438 2718 4381 1900 6283 135 2912 6862 7058 2020 6153 6332 8156 3412 8967 2811 2971 4458 9360 2255 2710 639 3572 3298 5865 775 5258 7241 9361 4146 5135 38 6547 3632 4825 4867 6334 640 9169 2480 4459 3430 5401 7805 9358 822 6974 477 2279 3256 8889 185 6950 771 2640 4792 6772 1190 4048 1129 2411 43 4847 3205 8984 296 5667 456 4829 5493 7975 3586 5589 6612 9385 2398 9001 5483 9300 1826 3348 3415 7485 2009 4287 4628 8265 2500 4045 163 5935 2592 7491 1529 6169 2256 5416 512 5740 8068 9441 3775 9040 1121 6037 3199 8586 5185 8993 4519…
Output: 7623

Example 3:

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

Constraints:

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

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