CT35325

The Hidden beacons of Emir

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the beacon hill of Lantern Tor, someone must rebuild the damaged itinerary. This year the task falls to Emir, armed only with the beacons register. 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 4 8 2 7 8 10 4 5 2 6 5 6 5 7 1 3 1 4 2 8 7 9 6 10 2 9 1 6 1 10 3 9 3 8 5 9 5 8 4 6 1 9 1 8 6 7 2 4 4 7 2 10 6 9 1 5 7 10 1 7 2 3 9 10 7 8 2 5 3 4 4 10 1 2 3 6 5 10 3 7 3 5
Output: 0

Example 2:

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

Example 3:

Input: 2 1 1 2
Output: 0

Constraints:

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

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