CT41553

Quin's beacons Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Quin inherited the loom house at the salmon ladder of Rushing Falls along with its curious bookkeeping system for beacons. Time to make sense of it. 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 1971 28 91 17 57 49 69 12 97 54 63 42 64 27 48 19 98 33 45 38 48 5 39 4 53 4 44 31 96 35 82 29 91 45 52 35 91 49 65 31 36 55 98 31 94 7 10 12 92 3 62 9 22 49 73 29 56 67 100 1 31 49 75 28 74 17 46 40 45 30 50 46 72 22 85 9 12 63 73 7 38 9 28 11 67 63 84 35 56 77 87 6 78 20 58 5 67 58 71 87 97 49 94 74 75 17 56 25 30 61 84 56 71 63 100 1 35 3 12 22 91 28 65 8 50 23 69 74 99 29 98 67 76 76 95 5 88 28 71 1 22 5 33 56 93 9 98 17 59 21 92 26 33 69 100 86 97 7 58 16 61 16 95 44 85 29 55 9 10 8 79 14 43 29 57 44 90 11 50 49 74 57 81 45 77 4 13 4 46 20 75 52 54 18 73 12 78 13 85 62 99 7 55 28 81 72 97 5 93 21 23 9 30 7 57 40 57 74 78 8 44 53 71 3 66 14 91 29 70 1 5 51 69 14 30 35 79 24 53 72 75 37 73 29 63 13 47 90 96 53 97 58 89 59 85 72 74 54 76 48 72 31 56 27 69 57 66 61 73 66 80 22 39 42 9…
Output: 0

Example 2:

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

Example 3:

Input: 10 9 1 5 1 8 6 8 8 10 3 8 2 4 1 10 1 4 1 6
Output: 2

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.