CT40025

Coral beacons Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the garden city of Petalbrook close for winter, Ranger must finish the beacons ledger - one figure at a time. 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 43 6 7 3 4 8 9 4 8 3 6 1 8 2 8 2 6 2 4 1 6 9 10 8 10 5 9 4 7 5 6 1 7 2 9 7 9 6 10 4 9 5 8 3 9 5 7 3 5 3 10 2 7 6 8 2 10 7 10 1 5 1 10 3 7 7 8 1 4 5 10 6 9 3 8 2 5 4 6 4 10 1 9 1 2 1 3
Output: 0

Example 2:

Input: 10000 1212 6784 8816 7627 9719 1839 6188 3583 7945 6652 7974 3857 6330 5641 5824 444 5569 9821 9976 9215 9867 2233 6441 8689 9341 1977 8869 3583 5799 3466 9476 4696 5335 4902 5432 8770 9516 3212 9572 7207 7361 8080 9559 81 2557 1977 9074 7770 9947 4558 5834 6173 8716 1879 9493 38 9852 7580 9729 6044 8561 869 9407 3769 6193 6734 8231 5763 8508 5205 7055 8103 9900 1984 9863 3396 4185 6550 8776 5365 8907 6059 8203 92 7120 3048 5873 5169 8778 1026 2801 3485 5711 6324 7413 2722 5724 1815 9998 326 5121 6619 9209 3056 8380 3449 6245 4776 8427 5608 8158 2545 7455 4517 4780 7741 7861 1505 1601 7587 8993 537 6685 5298 9977 4943 7685 7221 7454 5461 6112 1028 2661 2978 7007 1807 4936 3884 8196 336 8451 2531 9541 1221 4825 1794 5566 6076 6505 2117 4575 8383 9523 4086 7267 3121 8258 760 1925 3339 4411 9…
Output: 8787

Example 3:

Input: 2 0
Output: 1

Constraints:

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

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