CT40296

The Link Budget of the Celestial signals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The clerk Kian has been asked to track down a clerical error. On the desk lies a long table of signals readings. 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: 10 43 1 2 6 9 4 8 4 9 4 10 1 8 1 7 5 6 6 7 7 9 4 6 2 8 2 7 9 10 1 5 3 6 3 10 5 7 2 5 1 9 8 9 3 7 5 10 2 6 3 9 3 5 8 10 3 4 5 9 1 3 4 7 1 6 6 10 7 8 3 8 2 3 2 10 2 9 1 4 2 4 4 5 5 8 1 10
Output: 0

Example 2:

Input: 2 0
Output: 1

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Link Budget of the Celestial signals - MEDIUM Coding Problem | CodeTikki