CT41084

The Crimson signals of Chavi

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the railway depot of Cinderline pays by the answer, and Chavi intends to earn it. First: the full register of signals. 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 1 1 2
Output: 0

Example 2:

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

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Crimson signals of Chavi - MEDIUM Coding Problem | CodeTikki