CT46139

Nina's Crystal Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the northern keep of Frostgate; Nina weighs the day's registers 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 1404 14 79 8 33 30 72 22 23 48 54 13 21 68 93 34 66 5 61 18 76 87 97 20 57 1 48 22 78 29 67 25 37 4 60 75 82 41 69 48 83 21 49 9 99 52 62 3 78 70 94 18 89 9 26 30 63 79 90 35 45 52 74 51 58 6 88 57 67 41 82 26 81 7 87 10 22 3 9 79 87 25 30 42 95 26 55 70 88 42 45 62 84 12 36 27 36 15 74 39 77 3 90 69 87 21 34 13 23 30 59 6 7 4 50 32 77 37 64 8 62 18 93 30 55 16 46 16 86 42 50 11 78 27 41 46 50 27 52 32 47 17 73 69 83 10 95 27 86 33 69 46 74 8 96 43 79 70 89 43 89 65 90 21 52 71 91 7 77 50 79 30 43 48 58 3 15 4 9 1 29 19 50 3 79 18 44 18 68 75 99 78 95 29 51 9 16 36 67 83 86 26 96 20 63 12 18 50 61 25 32 20 65 10 89 26 100 73 99 48 74 17 24 16 53 64 100 28 34 21 50 84 97 30 100 60 94 54 100 6 41 54 80 55 77 30 91 46 52 13 61 43 69 70 79 4 56 15 50 34 94 5 44 6 15 36 61 57 98 23 94 5 71 …
Output: 0

Example 2:

Input: 2 0
Output: 1

Example 3:

Input: 10000 3123 2628 8067 143 8965 4197 9359 5230 8793 2576 4995 856 8076 7260 8127 3881 5032 327 3829 3593 5677 1400 2187 408 8954 2817 4859 2004 7342 1059 4976 1599 9782 359 4215 777 1978 2318 4117 1949 8182 1553 5678 563 9764 885 3513 2362 2695 514 8245 4255 8033 5295 8280 314 9845 3867 6945 4957 9021 754 8761 8702 9148 2935 4738 1154 9800 347 8707 7134 8203 3421 5270 3016 8952 4161 8313 2321 9694 4048 7259 2155 7041 860 5806 4798 8319 3196 6026 1818 5527 4452 7965 5826 8402 1561 4661 546 4086 1624 7235 1298 5571 4926 5362 1324 6844 7387 9037 3662 6581 3059 5857 6012 9771 1603 6914 168 1904 1274 4428 5254 9577 7909 9848 3917 5324 5297 6453 4014 7602 2226 2910 1941 3123 5483 5847 4254 7579 2055 5726 980 6384 5734 8833 1873 5540 4949 7522 7522 8041 6549 8701 4806 9163 839 4020 3070 4383 7760 9…
Output: 6877

Constraints:

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

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