CT38565

Ashen marks Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the herring shoals of Silverfin opens only for a perfect tally of marks. Zia means to find out. 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: 100 2051 3 47 61 94 29 86 22 33 73 91 95 100 3 40 20 100 16 68 1 33 35 52 41 92 33 59 1 76 14 23 9 78 23 53 22 86 34 44 61 83 3 94 46 78 22 76 44 90 18 38 2 84 75 77 68 72 1 88 9 83 15 21 69 72 53 66 91 92 39 71 20 27 56 62 83 91 23 55 20 87 38 49 23 43 16 95 38 58 11 63 29 47 42 94 60 66 70 86 45 62 26 55 15 86 2 42 83 100 68 76 58 89 25 32 28 75 76 79 79 82 15 57 5 52 75 85 5 21 60 84 23 60 57 71 41 80 36 56 61 74 58 64 53 99 65 71 5 73 37 93 23 67 20 64 1 62 9 98 12 14 41 60 31 92 31 42 33 56 60 73 8 28 10 74 1 52 71 96 52 97 40 75 13 88 59 75 8 12 43 79 30 45 57 72 58 59 31 56 41 61 14 37 32 78 25 68 49 75 16 74 57 96 8 71 6 96 84 99 43 73 2 8 13 52 5 36 28 95 68 96 25 66 11 77 14 79 49 88 27 37 16 22 43 67 61 84 10 89 56 89 71 75 37 52 61 81 39 63 33 47 44 81 94 99 58 96 61 96 5 43 55…
Output: 0

Example 2:

Input: 4000 3677 668 3814 423 3914 2495 3327 583 3939 3351 3573 2813 3302 1621 3888 858 3648 2351 3166 1549 3372 1976 3324 1285 3628 1656 1790 1656 3530 3843 3957 3079 3268 794 2344 43 822 1352 2229 1251 1591 2794 3659 2966 3692 3001 3992 1368 3802 2973 3210 2711 3674 418 1801 1283 2473 1807 2670 948 2536 498 892 3541 3752 1053 3973 2625 2875 508 3079 203 2562 1538 2383 2456 3041 774 1856 2667 2943 915 3747 1096 2660 944 2096 58 1075 120 2971 1867 3853 297 2941 618 2884 959 2698 57 2208 1633 2047 1009 2677 2121 3966 1095 1425 1309 1536 1531 1561 220 3991 3065 3479 2203 3940 576 1521 2155 3949 629 3059 148 2384 523 994 410 855 1294 2414 2596 2801 935 2840 3149 3935 406 2334 1983 3221 30 1595 463 3109 541 2606 595 1626 157 3698 1781 2336 1482 2696 242 3363 232 3004 2145 2159 1522 2369 510 1138 318 …
Output: 748

Example 3:

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

Constraints:

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

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