CT49986

Rhea and the Caramel signals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Rhea runs the loft at the gull cliffs of Screech Point. Today the books show a list of signals, and the numbers must be worked out before sundown. 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: 10000 1016 3047 9931 2511 4354 1959 9807 2674 8259 6455 7706 3981 4213 8353 8502 3764 9272 3682 7611 2453 8050 1500 8960 3180 6758 1585 8019 2362 2650 1084 7093 4821 5710 3449 7042 2165 3536 1694 8525 3151 4957 765 2613 8816 9221 3769 4679 3025 5621 603 3723 2828 7739 3658 4532 2029 3195 1859 8082 1633 5598 8970 9006 1210 5557 7323 9133 4186 6312 6962 8643 155 6075 892 2248 6335 7423 9241 9952 1637 1905 5819 9851 2487 8781 3952 8642 3547 9448 2124 7598 1535 7751 3220 8789 354 895 5177 6285 145 4050 4399 6023 3783 4546 5189 8273 4561 7450 116 9832 6370 7093 1740 7606 1534 8910 2638 9579 3213 5800 1975 9794 843 5229 206 3886 3053 4838 6216 6389 179 4161 1258 4490 4612 5138 7445 7950 6668 9746 3376 6582 3281 6181 1419 5640 2683 5593 3496 7542 3205 3476 1071 2003 4523 4999 3698 7491 3378 7559 …
Output: 8983

Example 2:

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

Example 3:

Input: 2 0
Output: 1

Constraints:

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

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