CT36668

The Link Budget at Saffronia

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the spice bazaar of Saffronia with crates of beacons, and Xanthe 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: 10 22 7 10 5 6 6 8 7 8 2 3 7 9 1 10 4 9 1 2 3 10 3 8 3 6 9 10 2 5 6 9 1 5 4 5 5 9 2 9 3 9 5 7 1 6
Output: 0

Example 2:

Input: 4000 612 2649 2917 2916 3518 1185 1226 1263 2240 13 3289 124 348 1808 2558 1218 3343 672 1950 2123 2432 1518 3237 1870 3820 1602 2934 914 2773 573 1104 1564 2612 263 452 3365 3689 1845 2160 706 1554 189 3041 2236 2629 398 2518 2809 2847 1775 3438 559 3804 2796 2969 533 2384 1260 2975 1264 2236 200 3217 145 925 328 2032 897 3273 901 3156 1202 2360 2474 2746 257 2874 1117 2176 1829 3915 566 1352 3557 3889 1094 2480 1866 3133 1316 3162 405 2434 577 1302 736 2456 2919 3697 739 3827 273 1798 2859 3530 1523 3590 793 904 1092 2301 1121 3783 124 1284 777 3107 3201 3865 1594 2961 2301 2589 1204 2251 789 3645 2549 3761 304 873 1392 2463 265 2787 1891 2801 363 3921 838 2453 3019 3217 3514 3716 1203 3943 1832 3074 3180 3311 1720 3820 1856 2093 3055 3248 1142 2869 3054 3792 686 2482 3248 3626 1890 2910…
Output: 3387

Example 3:

Input: 10000 3123 3907 8484 1055 2921 2395 7372 871 7656 236 7166 3835 7110 1304 6328 1765 2801 3974 4216 3886 3921 1198 8810 6111 7635 257 2618 5922 6855 857 6466 2467 8485 6464 7935 6734 9571 8593 8929 5303 5520 528 1163 201 930 6016 8871 3870 8949 3123 8022 3357 5559 1939 5428 1120 5415 2284 7991 305 8022 280 3618 4122 4734 4526 7633 4429 8421 2329 3889 733 4730 4423 6690 3411 6958 3001 9727 7680 9313 1818 1880 743 5326 3358 9611 1595 3030 1505 7594 4124 5215 3831 9635 3386 5490 2801 6657 3783 5976 8063 9435 3243 3652 525 4440 7451 8178 1825 3055 7498 7704 2919 8458 6765 7588 3025 9830 1408 4461 1752 3416 4874 7801 259 1116 4595 7868 716 3096 1668 7176 316 6437 3093 4750 6619 7160 563 8613 4828 6779 2581 5300 3845 7944 608 1022 43 8558 1065 4890 537 2685 2921 3178 630 7730 3024 7934 1915 4421 …
Output: 6876

Constraints:

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

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