CT56747

The Rustwood Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the fox den of Rustwood, Nyssa studies rows of registers entries. One clean number will settle the guild's oldest argument. 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 346 4251 7788 7046 8173 237 7346 6050 9437 3617 8284 718 1668 4236 7742 715 6628 2314 2640 320 2023 1443 4675 7096 7451 3189 9126 1009 2835 408 1579 487 811 1602 8764 886 3646 291 7541 3561 3824 3791 6409 3085 7452 8501 9755 549 3040 1302 5983 4745 4833 1910 5930 2098 6801 5002 7546 4274 8394 701 6676 1383 4674 1959 5270 3562 6979 3597 4777 6184 8395 2604 3120 6203 6782 3842 9897 2027 5892 7056 8712 8409 8413 3484 8649 1430 2804 1588 2319 4068 8105 925 1085 1347 4208 240 1981 4399 9253 2795 9518 817 2959 1534 6979 6722 9577 1528 8835 5313 9364 692 2906 5821 6799 2594 8268 4729 7691 5513 8737 1279 4762 2794 7212 2509 5953 3798 9844 5035 7604 2764 8252 2946 5393 3114 8089 1015 1465 2630 3864 2433 5097 4243 5975 2242 6220 2832 7971 1739 4046 4117 6408 3438 8279 479 6501 3018 8870 5876 7…
Output: 9653

Example 2:

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

Example 3:

Input: 10000 284 185 8724 699 2449 993 4880 1408 2701 4650 4776 2976 9531 496 6021 4935 8851 902 8278 1084 5993 3890 7638 6121 6499 7955 8464 3214 6638 5227 7908 2390 6046 8996 9542 2163 5024 3022 8298 3538 5062 897 4140 5325 9086 528 7622 226 9674 31 9562 1536 3293 7290 7430 5073 7016 3547 6166 5222 8526 1758 8721 2279 4671 4209 5830 1483 1506 9705 9888 3794 4262 3493 8104 1415 4220 1448 8149 2238 5023 7315 8262 1102 2023 966 7980 4284 9489 143 5786 1064 6273 4168 7388 5548 6197 1041 4816 2753 6774 3990 5154 5930 5943 4264 6078 712 4880 6186 7973 337 8039 1427 4461 5481 6177 1184 6876 4592 9567 4685 6520 1431 5372 5335 5644 7519 7787 445 6690 4073 6409 3042 7376 2244 8886 3645 3800 8480 9655 6853 8156 5201 6845 1759 9764 3477 4955 9585 9807 6554 8531 3441 9393 4473 5105 521 7149 2016 9855 1717 1…
Output: 9715

Constraints:

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

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