CT42169

Hestia and the Saffron marks

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the forest village of Briarthorn, someone must document the rare sighting. This year the task falls to Hestia, 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 3634 3450 3742 3639 3856 1010 1174 2770 3121 354 1378 568 3096 3432 3992 6 3779 65 3885 2420 2576 2020 2868 519 3309 692 1930 196 274 341 712 1243 1798 419 3277 1337 3788 2597 2613 441 2355 1497 3701 2080 3587 78 2152 868 1069 60 757 73 3371 1009 1520 1288 3699 969 1390 2333 2868 1102 1870 1495 2713 683 1646 290 3041 286 3026 1442 2299 2290 2565 1937 2694 2519 3337 753 1674 1112 2064 2823 2845 156 1010 1379 3096 858 1698 1192 3357 1159 2945 554 2758 1113 3057 1864 2066 181 2199 290 3946 2778 3324 3029 3875 3854 3863 876 3027 703 3355 1436 3178 1967 3493 82 2748 933 3895 125 1616 868 3487 2071 2296 26 3686 23 3606 1324 2920 2893 3356 294 3229 244 2996 210 3778 1161 3604 1101 1446 1354 3890 1018 3544 3166 3480 986 3685 345 2709 469 3525 265 1920 1360 3303 2016 3093 366 2961 555 2015 150…
Output: 775

Example 2:

Input: 4000 3771 1270 3323 1233 1708 683 934 2104 2253 1423 2745 883 1244 1498 3131 2483 3258 367 373 1750 1883 732 3541 2540 2641 1027 1824 660 2623 1318 2524 21 1528 220 3915 660 1052 2918 3792 282 3924 3264 3266 78 1512 391 1856 2368 2835 317 709 1298 2482 2302 3955 1392 2713 1275 3868 1078 2341 425 2066 887 2374 2932 3573 2360 3567 3133 3726 1486 3666 1095 1915 150 3703 326 2755 3055 3591 1280 3849 2671 2949 823 1274 2862 3930 141 1073 1749 1939 177 3110 2889 2937 1678 3981 260 2248 3575 3626 1534 2406 643 2222 2364 3657 732 3128 3459 3757 2503 3306 167 306 48 1707 2751 3732 2170 3916 1034 2534 697 3393 1251 2260 1188 2348 766 2912 1698 3613 1338 1802 2444 3781 123 1803 129 2963 584 1072 414 2727 693 1927 2238 3182 906 1383 2707 3956 1330 3518 1309 2823 1566 3513 1768 3553 1325 2628 1694 2462…
Output: 767

Example 3:

Input: 4000 834 57 2773 740 1149 1617 1964 2588 3797 2844 3844 1034 3635 174 3988 2444 3155 2214 3976 441 1822 499 3963 1042 1710 507 1819 1251 3457 479 1304 1509 2692 854 2225 2038 3497 3133 3206 838 1436 3142 3983 877 1241 1395 3671 112 1330 2168 2331 6 3662 716 2457 470 3539 686 2379 598 2270 2587 3884 239 483 1234 1410 3159 3890 144 3604 203 878 71 2240 3480 3919 2545 3245 1138 2869 2924 3138 3264 3327 1681 2283 2574 2861 2929 3606 2041 2500 369 3452 723 2024 2261 3455 2397 3435 750 2781 970 1853 1960 2450 728 2435 626 2957 1584 3944 455 2136 974 1451 412 2997 331 1707 53 3275 1546 1712 2047 3536 1457 1994 57 3878 1373 3427 3214 3508 1862 2277 1785 2248 56 3491 419 635 1694 3786 687 2666 640 1857 1249 3417 1067 3306 483 3825 2351 2935 1488 2088 1247 3100 2353 3324 2222 2693 937 3799 1598 3213…
Output: 3165

Constraints:

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

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