CT35999

The Petalbrook Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Koda the scribe watches over the garden city of Petalbrook's stores of signals. A careful computation stands between order and chaos. 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 2931 2163 2929 1380 3705 1752 3518 647 3997 2452 3114 1547 3746 594 1178 134 3363 1073 1527 1335 1433 1695 3868 685 2764 294 2441 640 1130 2173 3167 861 1323 2106 3892 691 3598 542 1707 56 3482 2362 3203 3251 3334 1351 3614 1790 2877 2698 2879 760 2798 697 1868 1686 1800 1380 2699 1841 2533 615 2080 2950 3544 100 3323 74 1440 1063 1757 27 220 1850 1981 238 1749 1343 2979 1351 3938 431 3371 1956 2342 182 2389 1732 1774 560 1988 480 1094 1160 2173 1493 1964 1706 2952 44 1826 2456 2754 1033 3609 682 3048 543 870 2486 2979 190 1319 2883 3701 1269 3939 396 2633 3358 3546 2435 3839 1371 1832 1154 2854 32 2236 1745 3094 376 2768 2185 3462 2113 3302 782 854 823 929 1580 3289 85 1950 814 3109 1410 1936 830 2887 2769 2955 485 1056 81 2860 1208 2173 38 1250 352 1423 1056 3958 331 783 1889 3541 2…
Output: 1173

Example 2:

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

Example 3:

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

Constraints:

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

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