CT40334

Cleo's Link Budget Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the kelp forests of Tangledeep close for winter, Cleo must finish the ledgers 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: 2 1 1 2
Output: 0

Example 2:

Input: 4000 557 2308 2764 786 2810 1447 2818 202 728 681 1459 526 2122 850 3008 2955 3531 1977 2714 1201 1935 2048 3983 1127 1346 1206 2273 2074 3665 721 3377 2245 2594 1161 2234 2496 2807 1090 3420 1290 3796 1844 3051 1236 1446 1314 1863 1076 3044 2711 3926 255 1892 1152 2871 2955 3130 1434 3047 1435 2204 996 2825 511 787 1004 2369 2405 3863 586 2174 475 3934 775 2244 2494 2499 2581 2935 1297 1446 2105 3954 253 2816 301 2704 1834 2678 1929 3437 2350 2812 378 2997 538 3934 863 1136 806 1279 2163 2898 1163 2473 3511 3538 730 907 520 1773 959 2683 818 2988 1421 2820 999 1421 295 619 294 782 2848 3718 299 2774 1847 2575 661 857 1669 1999 410 1263 1451 2731 1613 2926 1030 2928 2726 2758 907 2227 1192 3513 3394 3927 187 1579 180 2371 2941 3524 28 1692 3380 3590 529 2058 2188 3211 954 3976 2189 2891 10…
Output: 3443

Example 3:

Input: 2 1 1 2
Output: 0

Constraints:

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

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