CT51610

Diya's registers Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Diya runs the print shop at the smokehouses of Brineport. Today the books show a list of registers, 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 3947 5828 6045 5328 7991 518 3004 2258 4345 5678 9449 5396 6412 429 7634 1089 5873 8909 9145 715 3845 2391 9876 2003 3851 2200 6523 6292 8352 1715 1912 3361 6883 3191 7310 3755 7205 1790 7816 589 7094 3219 4988 6111 7780 7654 9762 787 6617 1621 8577 2970 9261 222 263 2121 7515 371 9616 7797 9748 155 1759 2340 3184 3673 5280 2795 4823 915 8760 4579 9451 1228 4362 5975 7157 547 615 4641 4696 6069 8546 6004 9747 3519 5855 3111 7574 1570 7944 1097 3307 3683 4484 2820 6072 4596 8831 4039 9854 8858 9666 6270 7106 6417 6431 4376 7385 2771 4676 491 4104 4377 4466 4183 7601 1908 7276 1477 4556 1814 4805 4300 6023 737 1947 1825 2331 339 7259 6439 9646 5954 6194 17 5186 103 1946 4046 5403 1929 2324 3891 4860 513 8307 7417 10000 603 3026 8491 8961 1177 7413 527 7050 7547 9706 948 1765 680 4629 5…
Output: 6052

Example 2:

Input: 10 38 3 6 2 3 1 3 9 10 1 8 2 5 1 6 2 6 3 5 6 9 7 8 3 10 5 8 3 7 3 4 5 6 4 7 2 4 1 9 1 7 4 9 5 9 8 9 1 4 5 10 4 8 6 8 8 10 4 10 6 10 5 7 7 9 2 8 1 5 2 9 6 7 1 2 1 10
Output: 0

Example 3:

Input: 10 42 2 10 5 9 8 9 5 8 1 5 1 10 2 5 6 8 4 9 2 7 2 8 4 5 5 7 1 4 6 7 2 6 1 9 2 3 1 6 6 10 3 10 5 10 1 7 2 9 2 4 4 10 7 9 7 10 1 8 1 3 6 9 3 9 7 8 9 10 4 6 8 10 3 4 3 8 1 2 3 5 4 8 3 6
Output: 0

Constraints:

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

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