CT55988

The Woven Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the garden city of Petalbrook, Bram the quartermaster keeps careful count of the marks. chart the migration season, every figure matters. 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 0
Output: 1

Example 2:

Input: 4000 2951 2388 3264 3208 3424 320 3426 444 2085 198 280 1366 2331 2115 2338 2182 3815 1432 3096 644 2804 493 2019 1691 2428 982 1666 1031 1551 52 134 379 2264 2350 3927 561 3233 240 3011 308 3908 399 2386 3027 3703 993 2829 1396 2056 2000 3099 1423 3982 618 708 524 2902 2233 2654 357 2264 1010 3556 410 1290 78 3219 299 628 214 3297 155 582 2244 3950 93 3253 1748 2944 885 1282 1919 3740 1415 3771 2387 2613 2718 3429 1392 3792 2695 3558 637 3613 661 3631 872 2472 1175 1463 2104 3909 2761 3766 1665 1822 1170 3894 2537 3535 2192 3345 1904 3385 827 3821 2582 3949 489 1399 2044 2287 3063 3335 1122 3688 2148 2363 1733 3937 643 1908 1500 2868 1246 1798 783 1903 1051 2933 6 3849 5 1544 889 3734 1957 3001 179 2099 82 98 191 2242 48 2187 1326 2335 965 2969 1844 2833 1282 2499 1885 2927 621 3115 689 2…
Output: 1168

Example 3:

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

Constraints:

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

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