CT49906

The Garnet Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the archive halls of Scrollkeep as Dora unrolls the day's manifest of beacons. 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 2621 2463 2654 1029 1742 630 1777 2172 2421 1407 2809 2903 3900 2199 3779 1076 3397 483 1688 617 2367 1328 3920 799 2254 1726 1915 3278 3436 3054 3825 2567 3078 166 850 899 3328 394 3448 1110 1435 275 1826 200 2619 61 3872 2606 3338 1012 2869 424 3766 1383 2742 3648 3844 919 975 3622 3678 1550 3397 1427 2226 2870 3009 943 1037 2874 2938 927 2218 566 1688 872 1766 1044 3444 3394 3966 435 2967 2789 3963 3876 3931 583 2504 1668 3581 2470 2635 1926 2898 806 2863 1710 2934 701 1985 524 1510 13 1482 768 991 970 2535 2759 3317 349 864 408 1610 2056 3689 49 1299 1069 3582 1943 2298 1141 2535 1455 2953 545 669 479 487 654 3663 922 3775 3230 3440 572 2764 1306 2889 244 1343 1542 1618 548 2152 279 301 1223 2932 1881 2121 2062 3969 370 3300 1189 3228 206 1787 1861 2610 2341 2816 906 3972 352 512 …
Output: 1413

Example 2:

Input: 2 1 1 2
Output: 0

Example 3:

Input: 10000 562 3247 4300 747 2094 3493 5957 2424 2769 1555 4925 8013 8668 7720 9133 1166 6496 6685 9046 2837 2867 8935 9024 4953 9381 276 671 879 2385 1704 1749 1949 6519 2594 9823 7435 9692 7073 8087 7050 7099 39 4081 260 7254 7538 7946 3052 6166 3015 3301 8403 9418 8479 9852 657 9825 3071 6596 1455 2669 804 7430 642 6770 1162 5796 1957 8002 1565 3779 4781 6625 568 1167 5471 7108 4200 4553 4270 6853 982 1066 161 9469 2069 9169 2297 2580 6073 6186 4927 6845 2656 4028 3028 3055 1851 9187 2458 7217 303 2285 6855 8359 1464 2384 592 8934 2216 4139 2395 9445 5535 6814 138 8727 5221 7636 5406 9662 1613 7862 7784 9790 2117 8631 1542 3431 7263 9229 1590 6175 9562 9587 3848 5599 1623 5432 1336 6760 4559 7233 1636 5949 6197 7189 535 3215 484 8891 5718 6898 691 1108 3566 8210 700 8842 4193 6695 1376 3177 …
Output: 9437

Constraints:

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

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