CT40285

The beacons Link Budget Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the mangrove channels of Rootwater, Lamplighter the valuer keeps careful count of the beacons. Prove the quality of the harvest, every figure matters. 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 15 2 9 2 8 3 4 5 10 4 6 2 4 1 2 5 7 4 5 6 8 1 7 3 7 1 5 4 8 4 7
Output: 0

Example 2:

Input: 10000 3865 95 4278 8983 9816 6749 8040 4637 8505 5485 6093 2282 4448 7286 8180 4391 5344 783 1795 2713 9953 2173 8072 6825 9884 2293 5598 4553 6948 3443 5563 680 3354 7795 9563 210 8704 3784 7606 3741 6535 1447 4574 436 7690 4983 6646 554 2166 5980 9574 2923 4435 5464 7170 292 7502 470 1356 7403 7646 6805 6987 3259 5869 5173 9143 1999 5431 7409 9307 6787 9067 43 5645 4971 8670 1729 6002 6824 9493 5597 8543 919 5728 207 4328 620 9389 142 8947 1467 3674 622 1109 5685 9131 4324 9554 6273 6457 8748 9669 6323 8218 971 3762 1427 7151 3515 8592 1266 2795 5232 9356 2808 6687 959 2996 4693 6453 165 3723 2136 4240 3787 9298 226 864 2540 4932 9265 9734 3487 4790 1960 7669 560 1587 1089 5828 1693 3240 6794 7828 5346 6368 5989 8980 7956 8776 2652 2841 5337 7653 1110 1551 172 1605 1052 3859 1006 3218 40…
Output: 6134

Example 3:

Input: 2 0
Output: 1

Constraints:

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

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