CT56329

Morgana and the Wayward ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morgana the factor watches over the crystal caves of Luminar's stores of ledgers. A careful computation stands between order and chaos. 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 1516 73 94 28 44 44 57 12 22 84 99 26 37 74 92 85 88 23 92 65 94 7 73 15 78 64 79 61 78 6 60 77 78 8 46 23 50 42 60 3 79 11 92 37 51 8 78 16 63 58 59 34 35 22 90 28 78 47 92 7 56 2 64 16 36 35 64 15 32 43 45 10 50 18 56 68 82 35 85 28 76 18 23 4 37 13 58 3 72 43 47 26 66 26 54 36 81 26 60 2 16 11 13 44 61 9 73 56 78 42 81 49 74 49 96 89 92 9 67 14 61 5 17 55 67 19 61 24 50 1 33 3 42 42 62 8 72 18 64 2 99 66 95 41 89 38 83 51 55 6 51 95 97 44 67 18 81 9 72 13 26 12 40 22 85 18 49 54 90 51 65 38 75 40 75 53 63 70 96 6 99 9 49 56 98 8 76 18 34 43 82 43 69 44 72 31 82 73 75 1 11 24 52 5 15 73 79 14 22 42 65 10 56 18 52 18 36 7 42 32 35 10 32 64 100 25 53 71 94 26 98 60 84 76 98 24 46 22 57 51 64 61 67 59 65 56 99 20 54 1 25 70 92 33 40 54 66 71 90 61 70 7 62 28 29 63 70 81 91 24 49 35 55 1…
Output: 0

Example 2:

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

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Morgana and the Wayward ledgers - MEDIUM Coding Problem | CodeTikki