CT43142

The Starfall Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the observatory of Starfall opens only for a perfect tally of marks. Farhan means to find out. 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 44 1 3 1 2 3 5 1 5 7 8 4 10 1 8 5 10 7 9 3 10 2 10 3 9 6 9 2 5 3 6 8 10 1 4 6 8 5 8 3 7 7 10 2 9 4 5 9 10 5 6 2 3 2 7 1 10 3 4 3 8 1 7 4 6 6 7 4 8 4 9 2 8 2 6 1 6 5 7 6 10 1 9 2 4 4 7 8 9
Output: 0

Example 2:

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

Example 3:

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

Constraints:

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

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