CT52336

Last registers of Cartwright

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Cartwright found an old ledger of registers in the apothecary attic at the lantern lake of Firefly Mere. The margin notes pose a precise question. 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 2828 18 50 12 57 13 23 29 82 4 84 21 22 17 95 3 13 38 92 52 73 29 95 24 71 13 88 39 63 58 74 52 75 77 79 32 50 21 51 37 74 23 93 37 70 11 49 5 73 24 37 76 87 26 77 27 98 28 61 72 95 60 74 46 56 21 94 34 81 59 60 37 73 10 63 1 86 21 72 24 65 91 100 6 43 52 69 87 88 21 50 5 25 38 99 53 98 30 85 5 19 36 82 40 61 43 54 32 94 15 89 5 75 29 49 46 90 11 95 26 91 36 78 43 46 42 47 72 79 56 87 60 81 80 98 38 64 39 79 73 92 55 82 1 73 7 27 48 82 19 70 16 58 48 57 39 42 11 41 4 59 39 76 19 63 4 67 10 98 14 63 16 48 40 71 29 73 38 44 23 95 26 80 30 75 86 90 26 65 5 68 71 82 11 72 84 100 16 20 13 98 53 58 65 71 3 56 79 89 47 89 11 50 5 31 27 56 1 39 16 75 82 100 63 72 75 90 63 79 18 63 70 89 49 54 47 52 26 43 21 60 29 40 62 76 15 23 80 96 58 60 49 67 3 16 36 49 48 86 33 59 45 58 25 92 16 30 56 95 1…
Output: 0

Example 2:

Input: 10000 119 2589 4819 7016 8316 1824 7191 7005 8641 4465 9669 874 6597 587 6124 1663 4981 1543 6517 1311 9818 5454 9717 7540 9656 5350 7773 5147 5308 790 9804 865 6262 2459 8318 5859 8706 1185 4894 5829 6588 4700 7724 3561 4043 1874 5634 7009 7634 3926 5472 6985 8907 465 9344 6115 7630 3463 3800 5490 7137 2283 7585 342 6003 868 5704 2877 4044 7975 8495 4112 8439 3605 4356 7922 9926 4923 6563 6078 8174 2381 6901 6291 8877 2931 5092 520 6106 1858 5195 3237 4466 3689 9178 2688 8722 8459 9306 5500 6222 476 6695 5 2012 708 1781 1617 6861 4687 5351 4114 5343 128 9214 2329 9599 3318 3612 973 4774 6227 9473 1229 8816 820 8565 9604 9627 2768 5142 287 8713 43 5217 8162 9449 4477 6767 1333 4367 110 2589 2369 3270 9013 9576 6117 8469 7925 8141 8494 9487 3537 5387 4230 6087 3693 9602 4792 6115 199 6050 6…
Output: 9880

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last registers of Cartwright - MEDIUM Coding Problem | CodeTikki