CT42865

The Scarlet Plain Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the poppy fields of Scarlet Plain close for winter, Shepherd must finish the registers ledger - one figure at a time. 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 2671 3 50 38 71 6 26 21 94 2 25 37 76 52 80 29 58 94 96 25 49 44 97 21 42 54 84 21 81 40 49 21 47 55 57 67 76 38 63 12 61 14 45 82 85 32 74 48 53 37 74 8 55 8 83 68 94 9 29 17 67 58 84 10 67 37 60 48 70 24 82 13 90 58 92 9 62 50 63 28 67 5 27 41 51 23 99 5 81 45 87 71 93 58 72 48 72 39 89 70 89 73 91 26 67 52 90 25 61 37 41 13 43 69 72 5 29 82 95 34 65 36 84 30 62 34 57 27 64 21 83 13 31 39 60 36 38 49 98 22 23 22 25 66 70 24 68 56 86 77 95 70 96 53 56 55 92 18 55 38 44 7 35 1 30 24 77 18 78 68 74 57 97 66 68 14 19 4 65 36 94 5 95 48 58 66 71 43 79 25 34 14 57 49 99 68 86 24 96 81 91 13 24 30 96 20 50 77 91 48 51 34 63 60 99 34 58 52 73 31 57 4 17 38 46 46 60 10 97 8 52 1 8 60 76 25 28 9 40 39 64 70 82 50 97 7 27 59 72 60 69 20 93 33 63 40 69 40 76 31 38 74 100 70 90 10 59 10 55 58 62 …
Output: 0

Example 2:

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

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Scarlet Plain Link Budget - MEDIUM Coding Problem | CodeTikki