CT56200

The Link Budget at Lodebarrow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The quartermaster Gail has been asked to prepare the expedition manifest. On the desk lies a long table of beacons 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: 10 38 2 8 6 9 6 8 9 10 3 5 2 9 2 5 2 7 1 9 2 10 1 8 5 7 3 4 5 6 1 6 4 6 3 8 5 10 1 7 1 5 1 4 2 6 7 8 2 4 1 3 4 10 3 7 4 5 4 7 3 10 3 6 3 9 4 8 1 10 4 9 6 7 6 10 8 10
Output: 0

Example 2:

Input: 4000 3563 1038 2429 394 3872 642 3487 48 1227 739 2876 1665 3244 2357 3397 203 2334 857 3931 1684 1720 378 3591 1657 2521 2660 3485 2470 3567 2712 2963 260 1432 1821 3384 2554 3869 180 3873 1339 3278 412 1485 1495 3022 1000 1402 415 3248 513 3613 948 1397 3196 3235 2292 2766 63 237 1363 3807 2969 3316 1848 3410 1935 2785 2118 2744 2311 3212 1050 2422 2033 2811 981 996 2345 2494 404 3845 265 2369 419 1237 651 1282 3098 3376 593 3108 2 3531 1827 3000 1778 3333 1719 1779 986 3841 805 1711 2211 3083 324 3343 1044 2924 524 3620 799 3865 1483 2489 1575 3512 1530 2631 444 1445 1630 2012 760 1216 2433 2807 1320 2401 2504 2611 2538 3447 1370 2081 2929 3853 545 3758 474 1711 1718 3480 1164 2734 376 2101 1938 3335 1038 1694 1465 3530 1798 2110 1288 1765 2496 3626 2386 3289 600 784 1446 3535 1450 3187…
Output: 813

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.