CT37875

The Link Budget of the Coral marks

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Lila found an old ledger of marks in the stall attic at the heron rookery of Longlegs. The margin notes pose a precise question. 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 0
Output: 9

Example 2:

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

Example 3:

Input: 4000 3110 3500 3938 2372 3564 1212 3684 1553 2049 250 3985 476 2656 756 3835 1562 1862 1835 3971 466 2836 1367 2836 1845 2933 761 2681 1575 2188 925 3588 689 2534 1766 2257 1041 3662 3301 3953 1240 1443 2760 3631 1357 3374 498 2722 1397 3935 281 1545 3585 3641 1423 3231 3297 3997 815 3024 2243 3941 2932 3350 1309 3540 2694 3058 1406 2138 1068 3337 878 3319 642 3884 81 3876 2744 3720 642 997 1060 2578 1500 3695 939 2462 354 3034 1679 1692 1629 1747 2725 3992 2780 3983 2081 2512 595 639 623 2669 1582 3193 316 474 188 1996 279 1760 1808 1972 1768 3583 1073 1145 1695 2432 1741 2889 364 1888 1357 2014 2172 2875 2235 3339 348 2253 160 707 760 2201 600 3828 489 3616 305 3337 148 3338 1214 1872 1226 1566 1483 3202 2709 3841 1851 3785 2198 3060 2223 2590 1176 2774 3033 3124 3197 3351 42 3920 3178 3…
Output: 1078

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Link Budget of the Coral marks - MEDIUM Coding Problem | CodeTikki