CT41514

The Argentium Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The assayer Petra has been asked to plan the harvest festival. On the desk lies a long table of ledgers readings. 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: 2 0
Output: 1

Example 2:

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

Example 3:

Input: 4000 990 972 1532 1761 3018 620 3964 2126 3126 1560 2743 1474 1632 2609 3155 242 2447 201 1696 521 2594 737 2550 494 2752 331 3131 967 2796 85 2784 1607 1752 2404 3349 1873 3261 236 678 2232 2625 1443 2701 476 706 1652 2718 3616 3921 1485 3597 1706 2739 294 2270 759 2521 1840 3428 1395 1522 902 2499 1548 3138 930 3788 1041 3377 803 3690 715 3881 800 970 365 676 1505 3820 364 3216 1190 3294 1709 2441 276 2941 563 1411 920 3118 3473 3632 3509 3869 3492 3581 1518 3361 1168 3385 624 3674 1635 3518 2045 3597 197 3769 1014 1628 1432 2042 2857 2956 873 2261 86 177 926 3202 2780 3474 445 879 46 1415 2587 2978 733 3634 3420 3531 568 2824 626 3692 2122 3468 142 1249 2902 3038 40 2235 371 3355 1984 2610 833 3833 1182 3473 2029 3271 242 1641 2720 3890 2628 2787 1112 3410 2245 3663 1975 2744 966 3200 5…
Output: 3009

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Argentium Link Budget - MEDIUM Coding Problem | CodeTikki