CT54961

Aria Counts the beacons

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the obsidian flows of Blackglass as Aria unrolls the day's manifest of beacons. 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: 10000 1510 5191 5364 5357 8981 5177 8321 1750 9004 9091 9328 76 1382 6204 9140 325 9531 4222 8938 3196 7696 2488 6115 4100 6893 829 859 1477 5442 628 8720 5888 8874 3518 4673 3437 7485 116 9289 3790 5707 710 7811 418 4492 953 9104 5404 5541 595 5451 5791 9948 1265 4992 4769 7112 3040 3329 6850 8423 1329 4047 2714 4163 3328 8942 1697 8410 5554 8333 2514 8287 3946 6065 7415 9064 1031 1331 661 6011 2394 6361 2366 7249 1428 5653 1522 4346 6079 6639 8970 9959 4099 6476 3406 4634 1649 7100 4067 6833 3885 8635 4819 6813 2302 8299 5052 8430 3191 4239 2405 6285 5390 6070 15 1961 2792 6389 5977 7928 769 5704 570 8004 4758 8523 2360 7161 8089 8413 7130 7571 1939 9435 6214 8752 2972 8570 2473 9291 504 6995 3188 8595 2485 7608 1573 7678 2467 8901 2466 5002 2960 3804 6518 7108 6218 9199 353 1311 1920 37…
Output: 8489

Example 2:

Input: 2 0
Output: 1

Example 3:

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

Constraints:

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

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