CT49691

The Link Budget at Brineport

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the smokehouses of Brineport close for winter, Nyssa must finish the signals 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: 4000 2944 3121 3246 1284 3286 774 1180 1700 3576 1674 2717 1215 2049 1771 1987 241 2212 1468 2414 37 3510 1553 3587 15 2987 2488 2756 991 1178 2379 3977 2587 3419 2597 3185 485 1712 349 2222 1684 3017 283 2897 137 2974 2414 2928 497 3189 2347 3858 2316 3318 1910 3983 1196 2038 2347 3660 2907 3543 1155 2786 2033 2961 295 1909 1549 2443 479 2171 583 861 103 527 3132 3559 186 1191 968 1320 2725 3207 637 3717 1746 3698 2499 3199 1464 3251 2288 2645 2209 2562 23 2204 40 233 1173 3076 2652 3663 1841 1896 1012 2558 640 1290 1312 3268 213 2392 28 2412 162 3497 215 1868 3036 3047 3251 3541 20 1579 63 3858 860 1490 2355 2372 1313 1481 712 2352 27 3052 1350 3980 602 3845 322 1730 2332 3974 1046 1619 1969 3904 50 3367 1186 2544 307 2512 1281 1303 2429 3160 1229 3603 1184 1721 227 2440 624 2091 47 2742…
Output: 1194

Example 2:

Input: 2 0
Output: 1

Example 3:

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

Constraints:

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

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