CT36973

Owen's beacons Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Owen runs the stall at the granite steps of Stonehallow. Today the books show a list of beacons, 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: 2 1 1 2
Output: 0

Example 2:

Input: 4000 2096 696 3485 990 1858 153 2706 216 3458 2599 3462 370 1074 354 2166 1184 2278 2506 2512 159 798 1484 2968 1697 2814 877 2824 1858 3835 1774 3120 101 2198 2176 2465 1404 2217 1979 3721 2031 3630 400 2660 1334 1697 837 2517 1678 2651 729 1731 1159 1312 1216 3399 1414 2861 1092 3928 2425 3633 1206 2248 2677 3424 1707 3402 822 2830 2041 3186 1014 2764 1078 2908 342 2604 705 3617 2276 2434 1362 2965 1822 2326 1689 3925 428 1062 3098 3625 1300 1365 522 1869 29 1559 1874 3158 3277 3925 1436 1589 3361 3725 729 3992 3023 3718 1283 2885 435 1182 1860 3719 643 3382 1793 2430 424 1055 593 1265 1359 3833 1864 2822 678 3896 581 2773 2270 2621 66 1817 212 3184 631 1017 2703 3293 59 1422 1510 3449 2907 3009 3226 3911 751 792 974 1592 1662 1756 495 3442 404 2986 4 965 159 2109 2240 2423 2618 3572 159…
Output: 1907

Example 3:

Input: 10000 1944 2202 7913 1288 2518 5952 9657 4633 6089 5246 6625 2860 3038 842 2382 7217 9812 3362 6876 1409 1867 2953 6851 3842 9919 4163 9046 3576 7386 632 1442 3080 6268 5328 8774 427 8488 9209 9450 2892 3724 3137 6017 8741 8962 2794 5183 2301 5078 2222 7075 3625 8818 5072 5942 7379 8567 7897 9627 2904 8837 417 3634 4645 9826 6262 8422 279 5548 5861 5980 6838 7192 712 9805 3840 9527 2285 4679 4631 6067 757 5481 1828 5098 2862 9686 457 2966 3016 5056 782 9541 4155 8364 4683 8793 7296 9973 2055 8125 1743 9367 4644 9863 2992 5660 6949 7973 369 1461 6039 8883 2779 4337 1623 6564 1758 2965 2243 6847 3609 6538 8802 9118 3844 7225 2532 5987 4745 8485 3332 8552 1464 9554 6102 9425 894 5400 3391 7114 96 9835 7770 8801 1550 2543 5938 9276 6888 9204 3156 6277 5125 5601 804 3651 5295 6780 6236 8674 165…
Output: 8055

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Owen's beacons Reckoning - MEDIUM Coding Problem | CodeTikki