CT40396

Uday and the Northern registers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the mangrove channels of Rootwater, someone must verify the safety inspections. This year the task falls to Uday, armed only with the registers register. 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 3627 1401 2207 1318 3762 1614 3987 240 1591 881 3200 2343 3965 1520 3946 1379 2436 129 838 1958 3024 2019 3302 834 2804 2008 3811 1138 2945 1583 2883 1097 3310 1704 1957 2310 3164 2272 2544 969 3182 1610 2038 1700 3759 1954 2995 1402 1913 2533 2565 47 2817 1420 3669 627 2205 313 1597 2056 3213 2764 3671 2129 3766 1864 3038 1801 2915 523 1523 1177 2669 2089 2358 790 2520 930 2793 1749 3231 287 781 57 671 1975 3497 1197 1732 1 3318 569 1220 967 974 1124 3504 766 3905 1309 3237 1566 2332 3100 3646 153 1113 308 2460 709 2009 1498 3889 1925 2714 940 2296 2709 3575 2768 3675 826 1679 2786 3526 1510 2541 1622 3645 2708 3757 2179 3850 1109 2668 2226 3805 257 3021 3361 3546 439 3103 3111 3478 273 2388 903 2166 1571 3785 1079 2641 858 3979 1788 3780 991 3638 1026 3578 730 3698 1851 2674 3485 37…
Output: 826

Example 2:

Input: 4000 3131 403 3802 702 2780 2434 3632 1068 1908 1578 1792 2612 3406 1957 2201 182 3764 1483 1798 46 333 1878 3872 529 1320 2020 3790 1185 2291 2562 3557 1268 1973 921 3256 1 1703 1928 3981 107 721 376 3832 531 3466 337 2144 1048 2744 1890 3558 1967 3256 18 1410 799 3530 119 1464 441 3674 2087 3667 1128 2114 19 1550 2336 3016 1027 2381 2622 3650 2582 2782 585 1339 2035 3448 1063 1238 2038 2621 31 717 2526 3540 1907 2963 1948 2768 2654 3705 158 2127 994 2529 3213 3450 2499 2758 2393 3814 568 1793 1112 1657 2005 2532 612 1577 1012 2110 913 1442 1341 2878 914 1853 2633 3491 1971 3769 2313 3913 2117 3174 730 2323 824 3846 2321 2442 1658 3859 1240 3792 2808 2865 870 2020 2411 2633 1603 3973 423 455 2680 2753 1082 3188 2660 3403 2153 2201 2913 3883 1848 2556 3027 3558 130 3821 2150 3300 1336 3564…
Output: 1089

Example 3:

Input: 100 170 60 85 54 64 6 53 55 59 54 97 51 87 20 86 55 56 22 27 51 65 53 86 44 63 39 82 18 40 31 34 33 49 24 65 3 70 20 38 17 74 48 71 16 67 57 77 75 83 61 77 37 63 74 80 51 67 50 83 47 77 78 100 16 86 52 97 14 34 9 67 11 75 16 53 10 56 11 63 47 88 32 58 56 80 51 66 71 94 32 59 89 91 13 59 24 70 79 90 38 99 67 81 18 33 88 96 13 33 20 39 17 79 15 50 58 98 65 78 27 84 69 81 56 99 25 98 73 86 19 89 47 93 15 39 1 93 80 100 3 60 69 90 47 82 86 92 21 90 9 31 2 85 12 46 77 94 48 98 50 60 48 66 98 100 44 83 18 86 8 89 44 61 22 23 20 90 15 92 6 74 31 87 2 18 22 72 21 86 69 74 46 76 19 57 24 81 28 69 66 79 1 66 90 92 25 37 4 12 65 76 89 97 28 89 70 91 24 32 26 27 11 40 3 87 18 76 68 75 3 43 72 88 26 68 39 71 41 78 7 58 30 83 75 97 58 67 31 97 6 12 61 69 35 77 28 51 78 94 40 78 27 60 9 55 10 81 37 56 56…
Output: 2

Constraints:

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

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