CT52408

Asha's beacons Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the mining town of Ironvein. Asha spreads the beacons records across the table and picks up a sharp pencil. 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 1422 51 52 53 60 24 31 32 50 44 84 92 93 11 75 36 85 58 94 11 60 13 57 14 79 57 74 27 53 21 98 15 20 53 71 12 52 7 69 12 22 47 84 55 80 13 33 52 100 20 38 10 55 23 70 45 55 52 77 19 97 20 37 14 37 83 91 43 76 25 48 12 21 23 97 9 54 8 100 16 91 15 51 34 50 53 62 11 30 25 40 57 62 29 34 43 44 40 85 58 70 25 37 50 91 88 96 28 62 23 55 24 81 85 89 80 95 6 92 44 73 21 97 41 61 20 55 84 88 12 25 4 63 90 95 4 15 46 96 45 93 69 93 72 84 5 78 22 70 15 17 13 84 51 98 68 95 24 30 26 78 13 67 9 29 27 80 42 98 62 94 25 84 33 84 21 85 11 36 16 45 27 85 18 69 40 50 42 51 52 53 10 46 52 92 40 61 45 90 73 75 57 65 34 43 43 87 49 67 10 80 24 67 70 82 47 60 86 92 19 50 51 59 15 69 24 37 18 24 8 12 45 53 28 43 49 91 19 36 38 75 87 96 40 53 76 90 18 77 26 92 23 33 54 75 86 97 9 13 13 93 55 72 3 81 6 67 7 3…
Output: 0

Example 2:

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

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Asha's beacons Reckoning - MEDIUM Coding Problem | CodeTikki