CT55081

Elowen's Ancient Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the pearl fisheries of Nacre Bay pays by the answer, and Elowen intends to earn it. First: the full register of beacons. 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: 10000 341 2993 9007 949 5763 3148 3540 6726 6743 2134 5438 6115 7714 2748 7636 1962 5765 6475 7185 1390 2890 3199 6093 6190 8167 7030 8757 3510 4146 4158 4755 4587 8374 3833 7863 4357 5843 3921 7148 6547 8448 577 6239 185 2662 6625 8885 133 370 2446 6961 3354 9828 478 7222 2838 4056 3866 9042 1507 7701 5201 7591 1855 9507 4054 6858 6940 9962 1932 3734 8470 8900 460 8165 163 9301 1961 3243 5902 6759 912 3546 7695 8115 7121 8956 4692 6319 2482 7089 928 9274 4872 6874 8553 9375 4909 5904 3557 7727 4431 6055 104 4026 5452 9627 2875 8615 2386 6664 1273 2320 223 5327 6613 9396 4486 6266 3104 5505 2314 9572 2000 3376 782 7442 6502 9671 8348 9401 5467 7318 5503 7563 3030 7958 6611 7466 2569 5264 3583 5858 6021 7708 5371 7538 1179 5549 2191 4844 244 6087 6164 8501 491 9897 3294 8391 2713 3269 8968 …
Output: 9658

Example 3:

Input: 4000 2191 1718 3230 1940 2953 1988 3951 265 2360 1085 2758 664 3284 1192 3749 1227 3600 352 651 572 2279 1420 3469 66 1419 1831 2619 1858 2835 195 1597 898 2601 160 2386 112 1865 2992 3967 61 1914 859 3246 410 3950 1279 2846 2376 2959 3044 3705 1679 3872 1548 1776 2132 3858 328 496 3224 3490 930 1690 2561 3186 366 1278 1144 2183 1487 3045 613 668 828 3561 1931 4000 83 363 1770 2245 262 3507 609 1624 401 3083 329 3385 1014 1725 1035 2999 1381 2795 3298 3489 2699 3741 1220 1836 3395 3610 340 752 826 2280 838 2952 1667 1793 822 1961 1952 3233 944 2078 1319 1912 2387 3865 3517 3603 336 1006 608 3414 1238 1262 897 1116 2055 2856 1825 2105 314 2640 684 1997 1426 3991 2392 2746 365 3478 122 3983 1021 1840 2570 3328 1518 3574 1284 1301 2298 2635 1403 3690 547 1946 2596 3817 315 1899 469 2080 1344 …
Output: 1811

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Elowen's Ancient Ledger - MEDIUM Coding Problem | CodeTikki