CT42711

Wistful marks Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the mountain city of Highreach; Xara weighs the day's marks manifests and starts the calculations. 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 1157 23 45 66 83 51 55 77 85 72 81 35 60 22 60 10 55 35 96 49 84 15 45 46 78 52 78 50 57 66 81 10 91 13 69 6 63 39 40 26 74 25 45 19 93 18 33 81 85 31 99 60 66 47 88 46 50 12 77 45 93 20 81 24 92 64 95 31 36 45 50 4 5 86 87 43 56 35 59 3 95 51 78 15 93 44 49 5 50 4 53 55 62 68 95 31 52 34 68 8 11 24 39 6 76 9 56 2 28 26 45 7 22 41 47 24 37 10 31 93 95 70 77 59 83 52 79 3 73 77 86 67 79 72 79 39 100 3 6 5 29 7 43 19 67 8 29 42 94 28 88 17 95 77 97 15 91 15 38 49 77 25 49 41 79 16 40 55 89 4 93 10 26 69 87 13 54 21 82 43 77 49 57 17 79 10 13 43 89 43 69 26 73 77 87 5 33 2 52 62 98 8 12 69 76 1 7 36 76 35 62 37 61 22 30 8 91 9 19 36 63 24 98 63 100 3 34 53 73 6 25 24 38 1 64 4 31 16 28 4 60 35 40 88 96 71 85 18 98 25 46 18 51 78 83 32 73 68 90 23 64 34 70 17 88 57 78 30 87 15 50 2 51 42 9…
Output: 0

Example 2:

Input: 10000 3147 2715 6673 806 4553 2536 3571 1510 5928 3553 8110 8266 9621 5871 6542 1746 3719 1315 2708 1979 5979 2504 6177 1204 6159 5561 5853 4294 6242 1743 5332 1683 6862 7037 9112 7223 9871 2268 6265 857 3733 159 3793 271 8155 5861 9381 2480 5099 7026 7070 117 8678 2046 8143 3915 4274 3263 8844 797 1249 1919 3089 3320 9765 5919 6706 2150 6197 4536 9774 3996 9224 622 9703 2361 8739 5118 8010 4762 5521 989 6768 4666 7801 7665 8119 541 8114 5979 7957 2457 2550 1741 6102 5186 5981 5226 8122 3198 9425 4626 8741 6530 8351 3372 4403 280 8633 3480 9625 8350 8571 2731 7381 1676 3840 1394 6990 128 5292 2403 5685 1850 4545 6196 7553 343 1586 5001 6444 3036 7568 1234 7484 4978 9105 3410 8125 4899 5963 2514 3108 1552 6643 1494 7897 1479 9867 514 8627 2780 5343 3880 8391 760 9338 2582 5010 4479 8801 475…
Output: 6853

Example 3:

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

Constraints:

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

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