CT42077

Zane's Ledger of marks

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the terraced vines of Grapehollow as Zane unrolls the day's manifest of marks. The tally will decide the next shipment. 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 953 2 21 48 49 59 60 61 84 2 25 69 75 6 54 57 93 40 55 1 43 15 63 15 78 70 87 46 86 28 62 42 77 14 61 68 98 62 77 26 31 7 63 81 92 2 95 36 43 10 50 21 63 28 29 17 37 70 74 2 98 42 60 9 29 51 80 25 32 56 59 4 12 7 86 19 41 12 100 26 80 17 74 84 98 20 25 1 30 45 81 34 75 76 97 7 94 71 93 73 97 9 79 2 47 23 69 67 80 2 89 28 80 73 84 2 32 29 87 3 92 36 66 30 99 94 98 35 48 98 99 26 38 55 66 16 68 91 96 67 77 39 96 11 27 57 81 49 81 15 38 73 83 19 34 53 68 43 44 23 39 18 93 80 82 21 59 35 82 13 36 50 55 12 97 43 88 55 74 9 23 8 83 18 77 23 32 34 42 47 61 17 82 9 67 7 32 43 65 13 64 62 76 26 71 35 41 61 69 39 53 49 92 33 53 3 8 12 54 2 3 84 94 18 24 10 85 1 74 18 56 16 65 7 66 23 91 16 85 27 43 66 90 17 35 19 81 17 99 58 95 12 93 14 86 47 89 56 68 54 82 56 60 17 94 14 76 21 41 49 53 36 69 73…
Output: 0

Example 2:

Input: 4000 658 74 2617 2386 3602 80 3894 117 2864 566 2860 2153 2191 1670 1988 1257 1897 1227 2468 3161 3241 266 2648 2116 2333 337 3330 745 3376 629 2576 2631 3358 1500 2477 572 721 19 1535 684 2650 1751 1844 733 3647 2478 3185 157 585 807 3764 2578 3715 224 1030 307 2347 1478 1553 101 1580 896 1167 89 3418 421 3065 945 2292 1511 3478 2612 2814 1649 1849 545 3464 3486 3755 2642 3222 199 639 1190 2760 1378 2242 1317 2843 2291 3117 1379 3743 787 2649 1774 3810 3360 3510 893 1649 1166 2012 2939 3707 1022 1037 861 3928 1404 1921 1786 3253 155 1641 340 1930 728 1363 3435 3448 1322 2706 207 2375 2834 3136 324 2647 1357 1791 398 1182 709 3924 2155 3049 2363 2825 1582 1998 211 3093 637 1921 1036 2465 1415 3659 373 2327 382 700 501 881 994 2125 2153 2690 1273 2397 316 3899 1155 1349 730 2542 3741 3977 1…
Output: 3341

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Zane's Ledger of marks - MEDIUM Coding Problem | CodeTikki