CT39921

The Link Budget at Luminar

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the crystal caves of Luminar as Tracker unrolls the day's manifest of ledgers. The tally will decide the next shipment. 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 438 328 3619 754 1455 1085 2603 1503 2880 395 3438 1188 3893 478 2502 853 2921 975 3167 1553 2047 3783 3793 412 980 775 2883 899 1561 1865 2500 581 3231 2407 3219 1808 3913 1110 2156 1669 2410 2033 2250 3170 3294 2507 2663 785 3239 637 1491 164 670 3686 3774 32 3496 487 2146 838 2176 2116 3506 3466 3539 3020 3366 867 930 1536 2321 1505 2574 1990 3243 3355 3691 43 3606 1858 2656 1500 3953 1035 2835 891 1926 288 1548 1181 2210 748 1684 171 1015 1096 1508 610 3463 593 3824 930 2017 191 1963 351 1691 411 1844 2265 3964 1365 2723 2352 3736 1393 2722 2562 2794 3060 3224 1989 2030 1949 2990 867 1774 253 1255 1116 2617 560 2593 3248 3468 2285 3254 951 2792 1893 2783 3331 3435 2972 3989 914 1294 1071 2220 2258 3800 1608 3351 2162 3800 200 2962 2888 3689 162 1219 650 1239 3478 3708 727 3377 116…
Output: 3561

Example 2:

Input: 2 0
Output: 1

Example 3:

Input: 10 7 2 6 8 9 7 10 5 8 1 5 3 5 5 6
Output: 2

Constraints:

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

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