CT57000

Wren Counts the marks

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Wren found an old ledger of marks in the depot attic at the canyon post of Redrock. The margin notes pose a precise question. 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 805 8963 9883 5020 8646 2808 5244 2349 9786 4445 5577 1133 3970 5278 8814 3146 3544 5909 7804 2234 9946 988 1048 4185 9704 3830 5471 160 8342 2464 5988 834 5612 9306 9921 5804 9716 5268 9001 3430 9867 1132 2371 7547 9893 1526 3798 164 9108 1234 5845 3975 8995 1284 9194 5216 9733 7253 9457 495 4026 5823 9132 6690 9128 4507 7544 7964 9943 5391 6553 5378 6528 3311 4176 1391 4652 8883 9735 6724 8880 1001 5697 1117 9352 4861 9333 1225 7614 5435 6077 3554 7133 3042 5505 2711 4492 2666 7765 3031 5211 585 3812 294 9452 3242 9176 3026 4214 3674 8111 2578 8367 5308 6468 3364 9092 931 9136 2375 6176 73 6277 4575 9914 2040 7219 445 9540 2710 9919 215 3596 8613 8791 5611 5865 1184 6161 2042 5266 4173 7341 2412 7303 3150 6941 999 6460 2354 7156 825 5472 3157 9416 1311 3984 5179 7107 1202 6118 7288…
Output: 9194

Example 2:

Input: 2 1 1 2
Output: 0

Example 3:

Input: 10000 1816 5049 7811 434 1800 1979 2324 305 8398 4652 9369 6091 6661 8725 8909 596 3869 5341 7754 1761 4386 193 7683 8 1846 308 6784 2146 7192 4746 6400 3551 6293 3486 8363 3346 4871 3692 6425 2111 8617 906 5580 1235 9159 2054 4655 2344 4342 9293 9348 4901 8544 4546 6078 5630 9223 29 9754 6724 9105 6022 7712 6199 9926 2328 7754 5773 8324 434 7117 2532 8782 384 7503 4704 7341 673 3970 6606 8675 504 8713 1812 6783 3198 6346 853 3651 2675 8874 61 2509 3151 3508 8086 8614 3782 7180 1755 2885 3477 8090 2885 4454 2730 9014 5455 7189 1530 2253 1371 6611 5534 9076 5364 6950 29 6342 1148 3848 425 678 2904 6667 4934 8594 504 5640 5070 8177 69 493 298 2849 5194 7944 6213 8695 2653 9112 3897 4384 1460 9441 6288 7457 1037 6011 4886 8969 86 4563 6226 6620 484 5903 515 8758 122 1205 374 9303 3008 3447 12…
Output: 8183

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Wren Counts the marks - MEDIUM Coding Problem | CodeTikki