CT43655

Captain and the Pale beacons

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the river town of Willowford, someone must win the guild's seasonal contest. This year the task falls to Captain, armed only with the beacons register. 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: 2 0
Output: 1

Example 2:

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

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Captain and the Pale beacons - MEDIUM Coding Problem | CodeTikki