CT53455

The Driftwood Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the quays of Driftwood, Wren the inventory keeper keeps careful count of the marks. Restore an old family record, 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: 10000 972 2237 5378 1413 6958 3048 3829 6979 9075 4286 7631 5622 8227 4761 8790 1097 4330 1540 5980 2217 2705 8 7635 7784 9810 2096 3994 449 4431 2303 3750 2994 6622 3457 5731 3632 9828 5062 8420 1677 6896 1722 4787 3520 7974 3316 7486 816 1654 4686 6454 1587 7307 3647 3954 35 3136 5050 9189 4452 9924 7571 9238 2653 8923 5061 9833 8354 8376 3209 9973 484 1911 1746 6772 6133 9802 4947 6058 3210 3731 6830 9323 5335 7451 3601 6921 550 1580 9554 9744 2603 4667 771 4350 4062 7101 1403 9240 3488 9863 4702 7578 970 4689 8319 8988 2259 9344 7265 9298 1186 2582 6453 6774 5470 5703 4239 5841 3466 4602 4810 9063 823 6046 7002 8099 3473 4411 2326 9698 6735 7196 3828 9515 1025 5309 5131 6230 1041 4362 2800 8368 8503 9886 911 3885 6268 6522 8905 9806 6994 8783 4962 7053 4749 8856 1254 4496 7879 9997 566…
Output: 9027

Example 2:

Input: 2 1 1 2
Output: 0

Example 3:

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

Constraints:

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

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