CT56300

Beryl signals Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The scribe Axel has been asked to verify the safety inspections. On the desk lies a long table of signals 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: 10000 1943 2689 8110 4384 4847 5462 5847 2469 3968 1565 8157 5525 5747 975 5548 1950 8138 1849 5562 1154 7966 2662 8860 2220 8730 57 672 472 970 99 6826 4554 8533 5081 9363 3186 5103 3843 5598 4696 8544 520 9105 4148 5526 4523 5107 2635 9039 5140 7992 1074 5040 2931 8829 4761 7279 4269 5768 6515 7925 747 4339 2684 9094 972 7232 9200 9649 1480 6925 2500 9572 8856 8933 3525 5725 1105 8479 4241 6649 1126 3667 1558 6614 6590 9099 1930 6966 2833 3763 1236 2212 1351 3944 1809 1830 1105 9286 6116 8800 1104 2385 6053 6718 4984 9605 114 4186 405 7127 6607 9297 394 6000 8274 9177 6731 9904 3901 7056 4374 5667 8883 9116 2182 2595 3513 8632 5801 6091 4089 9083 4747 6372 5090 6058 702 8661 2657 5026 5970 7156 1791 8225 2150 3560 6598 7800 5045 5985 869 4482 824 3031 347 2212 3443 9561 6481 8819 6885 71…
Output: 8056

Example 2:

Input: 4000 3383 1804 3349 641 2630 1761 3189 2739 3435 3200 3661 1983 3590 1287 2671 1573 3006 1096 2414 373 2643 151 741 2856 3039 1253 2115 1959 3384 714 1941 929 1421 2943 3034 353 676 850 1743 192 987 262 1277 2104 3650 2447 3611 955 3576 390 798 2588 2898 600 886 1574 2660 787 1466 684 1277 3730 3979 598 2790 1908 2424 2237 2965 3104 3148 2108 3007 2555 3018 691 2424 869 3609 1281 2495 1168 2197 849 3028 1427 2569 2401 2791 52 1373 265 2284 1747 3571 3156 3419 2419 3588 2312 3110 2976 3239 2 1210 276 2214 89 1821 3562 3710 2618 3570 2311 3446 88 1799 66 887 73 3970 846 2793 1528 3201 647 3239 579 3401 203 1525 1684 3424 1953 2138 321 449 1421 2993 571 2332 3136 3137 230 2699 789 1120 2403 2572 1172 3691 213 2953 2075 2952 215 3402 300 3381 3142 3250 1558 2829 1229 2285 1987 2654 1651 3218 3…
Output: 922

Example 3:

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

Constraints:

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

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