CT50460

Rekha and the Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the marble forum of Argentium, Rekha records each marks in a worn leather ledger. The guild wants answers, not guesses. 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 0
Output: 1

Example 2:

Input: 100 2679 3 89 8 100 3 29 46 84 1 57 14 51 51 65 34 67 15 31 10 57 50 62 28 80 35 78 66 69 41 80 24 47 59 77 40 72 28 58 56 75 33 66 51 59 66 98 44 73 34 52 32 92 19 81 38 72 27 59 3 94 15 39 12 66 48 92 29 64 32 93 46 53 34 36 9 58 81 84 24 45 10 81 64 87 32 83 8 13 21 74 25 32 42 72 26 78 19 84 2 94 15 42 26 75 2 21 78 95 73 75 31 34 17 77 12 93 63 98 52 54 47 73 45 52 69 79 21 70 16 70 7 87 12 49 54 67 19 68 13 97 1 83 82 86 21 45 84 95 25 97 1 38 57 85 80 89 70 90 9 47 32 76 12 32 3 68 1 2 6 59 8 12 15 82 21 94 54 57 24 68 24 60 42 94 31 77 33 48 8 35 25 78 1 8 10 72 7 73 30 73 28 38 83 96 18 66 8 73 40 100 60 99 63 84 22 79 39 74 62 82 81 96 42 95 17 43 51 82 18 92 33 97 13 39 35 82 16 92 25 87 35 80 30 81 54 97 63 100 8 79 12 50 24 51 21 51 68 79 60 67 30 42 64 99 37 79 27 98 28 55 38…
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.
Rekha and the Link Budget - MEDIUM Coding Problem | CodeTikki