CT45848

Devi's Gleaming signals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the obsidian flows of Blackglass, Devi studies rows of signals 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: 4000 937 1358 2605 3479 3512 796 1877 2081 3738 1393 2747 801 2123 285 1910 313 3512 2214 3332 218 3395 1356 2567 298 2356 1713 2973 728 3430 1629 3358 2012 2990 2695 3378 1396 2107 2931 3909 29 1115 8 3376 1927 2068 2638 2783 1451 3228 2753 3116 1646 2753 3503 3937 924 2428 1168 1629 72 1115 1062 2000 252 1373 1476 1960 118 2700 2519 3169 708 2072 2156 2740 1660 2516 1715 3468 473 2748 1532 2295 482 3545 375 3208 374 907 1675 2139 1523 2915 2206 3478 1729 1827 2176 2489 2634 3408 723 1394 2340 2939 62 3671 2715 3297 3936 3975 1946 2224 553 3656 2070 3729 2108 2478 1517 2847 2780 3098 2660 2674 995 3842 1639 2055 259 856 619 1491 1553 1830 2317 3027 309 1659 1737 3167 752 1611 1425 3644 2409 3496 122 3847 2789 3655 1186 1998 1491 2882 2152 3716 1912 3399 1041 2336 531 3384 1927 2127 152 36…
Output: 3062

Example 2:

Input: 4000 2104 1275 3255 786 3644 730 1103 4 3594 787 3930 422 2645 136 3313 2238 3725 2171 2890 465 1450 988 1023 325 1553 1911 2768 2494 3633 1344 3930 1941 3063 985 3928 2602 3844 835 1585 117 3314 1431 2630 1115 1970 2525 2848 1383 2020 926 1347 2377 3099 1687 2877 1396 2795 799 1593 729 1214 389 2919 1894 3834 853 3176 355 1876 488 580 1584 3175 626 2332 700 3847 2853 3883 1409 3909 3330 3544 2653 3553 2441 2787 1990 2947 1291 1645 501 2225 3089 3663 1372 3623 904 3469 340 777 1203 3978 540 2535 2986 3252 610 3945 2198 3380 1258 2561 1063 2369 2135 2383 311 3870 182 3412 86 1087 1189 3043 1748 2014 88 3688 1141 1682 444 3510 658 2374 2182 3899 511 3013 1276 3009 1478 2914 386 673 79 2665 12 1475 369 1901 701 2462 2678 3258 889 2205 1762 2005 1666 2707 3130 3289 1635 1707 850 2887 1480 2927…
Output: 1898

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Devi's Gleaming signals - MEDIUM Coding Problem | CodeTikki