CT43707

Twilight beacons Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the tundra station of Whitesnow. Farmer spreads the beacons records across the table and picks up a sharp pencil. 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 41 9 10 2 7 2 4 2 5 8 10 1 5 6 9 2 8 6 8 1 6 5 8 1 7 1 8 2 6 3 4 2 3 4 9 1 10 3 9 4 8 4 10 7 10 3 7 7 9 5 9 4 6 1 2 3 5 5 6 8 9 1 3 4 5 6 7 1 9 3 10 4 7 1 4 7 8 6 10 5 7 2 9
Output: 0

Example 2:

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

Example 3:

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

Constraints:

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

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