CT47059

The Link Budget of the Gleaming marks

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the dune sea of Caravanrest with crates of marks, and Xavi the auditor must account for every last one. 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 781 862 1947 428 2941 567 1930 2234 3071 1216 1546 2501 2518 932 1494 1418 3857 1491 3946 1182 2449 3581 3759 818 2431 2457 2601 2535 3155 2024 2737 892 3229 50 1020 1881 2659 2429 2552 1644 2602 156 1479 1736 3238 2853 3911 1643 1813 2427 2942 410 3989 923 2685 394 3359 1396 2077 261 3353 629 2741 2543 3015 1294 2885 1278 1521 761 1540 1620 2082 47 225 2313 3399 522 2613 3029 3848 1385 3319 2474 3353 137 3861 17 954 1740 2146 1246 2290 1039 3264 2002 3615 1924 2971 444 842 1508 3165 1297 1962 581 1963 1520 3312 3679 3895 1243 3847 3213 3819 1388 1435 667 1044 1024 3127 3041 3500 539 2596 1906 3425 713 1317 837 3533 814 984 752 1345 200 2141 25 1686 474 3345 54 3897 2175 2849 35 2084 1184 1665 531 641 2331 3977 1645 1938 345 3747 866 3921 930 1236 616 816 955 3351 2306 3657 1637 3743 …
Output: 3218

Example 2:

Input: 10000 1817 1733 5079 76 9801 3368 6234 1604 6993 1810 3503 3670 8921 4424 9975 20 2120 2036 8934 8467 8798 1198 7927 5011 9305 1747 9213 3462 8871 724 8598 341 8768 3740 7689 6264 9942 494 3265 634 3960 3849 6938 5115 6164 3164 4686 8871 9146 711 5526 1408 2795 1261 3568 8856 8997 1103 5450 5064 7912 7866 8907 6021 6702 1062 5389 5794 8484 6187 8988 5482 7744 3746 6209 4773 8774 1522 5605 1802 9397 1315 6801 149 1594 4479 5177 4253 9157 5713 9297 2104 4894 2234 8641 2502 9995 1345 3429 266 8328 8597 9473 772 8502 8259 9257 5548 9348 2506 7052 739 5461 779 7396 1758 2340 1430 6916 5509 6697 7817 8891 1935 3712 4199 5070 4010 7944 1335 4393 6233 7975 2050 8631 5819 7424 1607 3694 152 2229 3121 9304 6368 7593 2353 9251 4323 7615 6245 7387 4503 8153 7793 8962 7923 8643 2175 6928 4630 6151 2840…
Output: 8182

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.