CT50518

Last signals of Bhavi

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the fox den of Rustwood, Bhavi the bookkeeper keeps careful count of the signals. Fulfill a tricky customer order, every figure matters. 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: 100 1760 57 79 31 78 46 75 4 74 17 92 3 86 64 88 14 99 49 92 2 60 9 63 10 78 1 57 10 31 69 91 4 82 36 96 15 25 3 92 6 87 11 25 89 97 19 30 33 95 47 78 66 93 7 96 32 93 8 23 21 85 24 72 34 55 47 54 2 29 16 52 58 93 9 66 41 44 18 38 50 97 10 71 32 68 64 93 41 57 21 61 52 53 39 99 44 54 54 58 84 97 11 41 13 23 64 76 82 99 3 95 12 55 13 56 12 28 27 84 12 25 71 79 48 89 88 94 62 82 2 72 15 81 25 42 13 74 5 86 42 43 25 34 1 80 57 91 5 68 58 81 18 89 31 57 14 87 41 84 31 99 55 76 14 61 71 93 61 83 27 82 37 77 30 71 19 83 3 31 74 94 20 57 47 73 17 96 8 87 48 99 55 65 48 95 73 94 84 86 5 39 16 45 19 68 11 35 2 85 2 52 31 68 61 65 57 70 31 93 31 84 44 48 14 16 67 98 34 71 22 92 13 77 6 12 34 87 14 39 28 97 84 95 64 97 46 86 3 30 47 82 32 79 3 53 48 73 27 47 35 38 22 31 53 86 2 14 13 45 7 35 28 77 85…
Output: 0

Example 2:

Input: 10000 3953 221 7353 7288 8155 2796 4119 111 2780 7553 9915 3921 7831 5261 8513 1698 4402 7452 8176 1467 8628 1760 9750 677 867 1310 9982 2234 2881 4170 8105 654 825 242 3570 1272 7974 7811 9134 5210 6271 3177 8433 44 7816 2826 4038 8795 9209 265 1931 4538 5866 3956 8207 4849 8154 4818 9383 6179 6640 6860 8665 2978 8390 3396 9971 4401 5939 3003 4385 138 3076 5624 8707 4945 9728 2881 4936 4206 5736 1784 7633 372 574 4339 5420 2563 5765 5572 8059 3980 5678 3177 5168 772 1560 6584 8354 3829 8742 320 376 3003 6623 3304 3991 2040 7552 3771 6959 5770 6040 2132 6377 2466 8548 3631 3999 707 3416 2137 2826 3360 9097 2810 8458 1752 1791 573 3862 5336 8416 3229 7554 6227 9149 8870 9520 1560 9658 1941 2481 811 7957 3033 9631 1343 8164 2468 4404 2865 3356 6483 6917 957 9976 4448 7441 3107 9664 1962 3899…
Output: 6047

Example 3:

Input: 2 0
Output: 1

Constraints:

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

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