CT35030

The marks at Mirrormere

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the lakeside town of Mirrormere, someone must price the new merchandise line. This year the task falls to Gita, armed only with the marks register. 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: 4000 2468 2253 3929 2760 2801 655 2214 179 2321 2317 3830 430 3997 579 3888 1234 3082 484 1701 243 2984 2734 3738 1202 2660 544 2937 227 1546 2374 2515 342 1768 2990 3832 2949 3033 306 2452 727 3838 3234 3607 433 2332 1049 1792 359 2380 1323 3404 628 3397 608 1113 692 831 1564 3768 692 3929 184 3617 2913 3826 2364 2801 1062 3924 2332 2548 780 858 2085 2764 444 2565 3050 3786 1709 1798 48 3111 3213 3311 355 1027 2507 3530 1254 1506 1506 3956 1352 2545 585 989 1528 3669 2196 2443 2799 3723 2339 2373 2589 2892 401 2731 1845 2599 2429 3170 1715 3837 317 2933 182 1035 668 2403 876 2693 903 1234 157 1148 2875 3639 1964 2167 1899 2129 72 1948 755 3430 49 3063 18 288 151 843 1634 2430 1033 1613 459 1289 574 1693 663 1623 1995 3179 1452 1821 2449 3054 1481 2046 221 720 115 2995 2477 2872 2786 3990 …
Output: 1557

Example 2:

Input: 10 4 6 8 3 4 1 2 5 6
Output: 5

Example 3:

Input: 10000 1181 2137 3977 1262 5363 568 6178 5065 6491 99 7754 3153 6819 4461 6102 1792 8712 1057 8190 8691 9847 755 2851 4403 9339 6067 6251 42 6001 24 4433 4340 7776 514 3965 3481 6922 4542 9954 11 1013 2575 6080 5610 6759 4316 8600 1595 5298 4174 5595 8519 8952 4263 8567 4307 6728 681 9086 7518 8898 1403 2481 6868 6945 5268 9195 1174 6121 1669 9224 479 7982 3921 5493 1096 2552 2500 3347 3041 5448 5987 9344 5980 6486 7589 7657 3748 5477 5944 7941 5361 5726 842 7925 1244 2944 4390 9358 3200 5680 3221 9088 3177 5587 2985 3347 3444 5894 547 1726 6875 7627 6063 7852 1597 6767 3934 8569 678 4090 2303 3149 2894 5948 3978 4951 3545 7169 500 2255 5 7539 1037 8647 1588 7672 2024 2864 1563 7439 3773 9287 577 6067 1048 4725 1512 6784 5824 6546 340 8015 7337 7555 945 7482 2820 6974 358 6354 4430 5744 349…
Output: 8818

Constraints:

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

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