CT43898

The Thimblewick Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the wren hedges of Thimblewick; Gautam weighs the day's signals manifests and starts the calculations. 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 1 1 2
Output: 0

Example 2:

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

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Thimblewick Link Budget - MEDIUM Coding Problem | CodeTikki