CT44943

Jeweler and the Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Jeweler found an old ledger of marks in the apiary attic at the willow walks of Reedmarsh. The margin notes pose a precise question. 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 3809 13 92 6 95 8 21 24 71 58 87 25 86 24 34 56 65 9 18 15 67 80 97 11 96 70 79 46 58 85 87 9 27 21 24 66 88 27 57 43 44 25 41 17 82 18 21 12 83 3 36 10 37 12 52 14 91 60 68 56 99 15 91 57 69 22 68 7 71 32 92 42 45 22 88 7 100 1 79 10 39 50 52 85 94 58 92 47 60 14 64 66 70 53 86 6 53 65 82 20 50 34 100 1 11 49 82 65 86 4 59 60 74 6 59 10 86 64 78 1 26 40 79 28 30 36 66 18 86 92 97 11 60 54 56 20 37 55 93 3 86 35 62 18 57 6 78 51 97 1 13 26 49 11 99 34 47 16 63 17 52 17 58 4 84 42 75 63 68 45 58 70 75 4 93 30 96 17 91 19 37 22 49 2 64 4 56 54 89 37 65 62 85 14 31 17 22 23 94 13 30 32 76 19 24 46 90 26 95 11 59 25 36 1 27 12 100 15 68 16 93 20 62 14 65 48 63 43 48 2 44 17 87 79 95 72 80 16 40 34 88 53 93 80 92 77 81 3 48 32 64 95 96 62 70 39 57 2 43 16 88 21 95 60 84 10 99 28 45 39 52 52…
Output: 0

Example 2:

Input: 2 0
Output: 1

Example 3:

Input: 2 0
Output: 1

Constraints:

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

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