CT51993

Dorian and the Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the peat bogs of Mossgrieve, Dorian the scribe keeps careful count of the marks. Track down a clerical error, every figure matters. 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 1722 9 39 54 94 27 35 18 28 60 92 6 95 24 78 22 29 23 61 44 95 59 99 26 91 11 48 36 97 63 69 17 93 21 69 13 85 19 30 40 54 29 58 4 66 1 28 21 38 37 51 17 22 5 90 26 35 38 88 53 56 9 18 10 88 7 21 66 90 82 89 88 98 94 96 75 100 58 98 19 24 43 97 37 63 19 49 16 54 87 90 53 96 41 54 36 60 25 100 12 32 1 35 17 61 1 85 91 100 3 88 98 99 30 98 35 47 32 94 7 29 36 79 57 100 23 100 26 98 32 90 32 95 43 98 28 84 55 59 28 51 9 24 24 30 9 48 28 57 12 47 74 92 1 91 14 27 40 48 72 93 78 97 13 59 2 86 58 85 67 98 48 65 58 60 60 81 20 28 31 99 18 55 52 90 16 83 21 89 13 57 76 80 45 92 41 83 3 92 49 55 21 71 50 91 15 73 15 89 49 72 6 38 5 50 40 90 23 47 33 67 33 93 34 100 8 61 39 49 2 74 11 20 32 34 5 61 62 84 25 72 63 97 4 46 56 87 71 100 2 70 56 57 1 99 34 93 28 97 92 99 32 82 14 67 6 48 14 54 48 84…
Output: 0

Example 2:

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

Example 3:

Input: 10000 671 3159 6316 1628 4891 1308 2334 3174 3809 2790 5285 3978 4473 5026 6507 1436 9619 1885 8182 196 8577 4113 8008 684 3406 308 4459 2791 3263 2489 6804 3771 5773 1796 3856 2615 8789 4927 5657 257 9063 6419 8446 6723 8751 5073 6503 6638 7257 1238 6546 4245 9010 744 5407 1524 2582 4984 7082 5863 6144 7481 9516 153 2941 2578 9133 4289 7264 374 7339 6223 7206 4492 6326 2409 9352 1768 8114 8908 9096 6440 8269 6131 8305 157 6301 3961 3976 6383 9085 2322 5338 5866 6523 2110 4187 5671 9472 5253 6761 41 429 225 2977 3117 3206 2794 2815 476 9510 8736 8944 78 6128 3586 9696 2156 9320 1773 4401 1812 3675 1370 5066 6862 8609 1707 2169 3317 6068 1875 5270 7575 9512 4321 7415 2113 2681 2932 5309 3381 9938 1910 4782 1642 2192 1271 7717 1732 9496 2708 8723 4573 5157 2178 5673 2761 9998 779 3112 290 10…
Output: 9328

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Dorian and the Link Budget - MEDIUM Coding Problem | CodeTikki