CT55374

Last marks of Dev

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the spice bazaar of Saffronia; Dev weighs the day's marks manifests and starts the calculations. 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 1555 3132 4000 705 3550 2134 3422 270 3543 48 3395 715 1572 949 3581 1255 1566 2814 3000 802 1261 364 1019 800 959 2057 2717 1263 3319 314 1617 430 2497 1265 3866 1927 3366 926 3232 2467 3488 249 478 20 265 1911 3224 583 2699 2934 2941 2161 2693 675 1061 1888 3376 2552 3226 437 733 424 3733 1141 1703 2535 2906 2600 2730 1372 2287 516 1187 2310 2522 1231 1539 2117 2626 1090 3263 2139 2928 688 2318 922 1478 2766 3038 278 3201 376 2308 717 2834 1169 3054 76 1767 457 3255 964 1550 1118 3423 715 1626 2131 3475 1705 1855 678 971 1519 2189 685 3068 713 3745 366 1397 172 1782 1381 3231 920 1813 224 3039 1970 3232 3052 3925 1007 1434 18 1240 2614 3071 302 2988 216 1935 1439 2783 167 2273 362 1676 1542 1646 837 2757 797 2912 726 798 133 1385 1759 2977 1225 3869 2152 2399 2953 3390 1411 3206 324…
Output: 2444

Example 2:

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

Example 3:

Input: 2 0
Output: 1

Constraints:

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

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