CT44412

Morgana's Garnet Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the mountain city of Highreach. Morgana spreads the marks records across the table and picks up a sharp pencil. 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 347 819 1803 2826 3487 2231 3143 559 3201 842 3393 1668 1916 388 1677 753 1391 113 1798 206 618 547 1476 1158 1682 2405 2832 2317 2617 1702 2817 862 2347 1725 3504 565 2396 691 3573 81 1136 1589 3894 354 2779 1368 3575 947 2256 222 2445 2552 3619 709 2507 1942 3076 1156 3667 2428 3651 736 3498 1648 3389 153 1213 38 1237 487 2424 121 3622 2582 2684 319 1137 2435 3199 1294 3311 175 1616 2675 3850 1442 2002 2140 3653 664 1587 1547 3743 1241 2673 1719 3826 2351 3294 1934 2247 1862 1936 1964 3318 804 1613 1231 3719 2224 3603 968 2355 901 3460 2059 2869 609 3045 1121 1168 374 3553 706 2744 260 2752 2969 3701 3041 3852 1410 2202 2146 2992 158 1848 580 696 1429 3012 959 3238 204 3566 166 937 121 3918 16 3101 1285 3695 994 1645 1051 2211 564 2144 429 3450 1528 2819 1818 3792 650 3013 2468 3664…
Output: 3652

Example 2:

Input: 10000 3405 3782 4717 824 4728 5301 8741 2169 8287 446 8244 894 7079 6569 6796 2099 6558 3365 7263 2154 8267 208 6262 3178 5219 332 7965 6607 9693 3787 8818 3027 4829 4690 5478 4869 7873 2033 7267 158 6356 1950 4515 2200 9194 3918 9806 4159 8867 8981 9579 6235 7977 1577 2381 3017 7768 1757 6729 2622 7612 2355 9378 3452 3694 5416 8141 392 6608 4273 5230 2561 8977 3685 4299 2908 4300 1696 2275 1456 1782 1967 5010 1456 3292 3884 4745 297 7428 473 9741 1898 2329 4317 5199 1024 7615 8209 9455 3075 4009 6247 8055 764 8776 1772 4131 5814 5935 1542 6424 1183 6155 9193 9753 2019 4849 6791 8825 972 9279 1112 3100 7936 8143 4868 7294 7975 8355 202 5191 572 5620 4494 6216 4536 8351 938 4031 4687 5376 195 7009 2101 3786 7337 8273 4712 5527 1311 6351 3023 7344 2537 4149 997 2131 3406 4561 2205 9450 1525 …
Output: 6594

Example 3:

Input: 2 1 1 2
Output: 0

Constraints:

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

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