CT56107

Marek Counts the signals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the cork grove of Barkhaven, Marek studies rows of signals entries. One clean number will settle the guild's oldest argument. 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 3942 2450 5996 1989 9735 9272 9348 808 9276 76 4400 3437 9006 6412 8677 551 4458 6009 7003 4629 6101 3733 8760 4679 7750 2342 6753 2528 8567 3266 5682 2978 2987 8713 9615 1600 6524 5265 8635 7985 8440 367 3835 5893 8588 1472 8395 1641 7091 3350 4433 432 8109 826 9965 7945 9037 4845 6923 4629 6028 5037 8168 1832 3353 548 7984 7551 8252 561 1718 3124 4486 6693 6704 503 1796 84 5605 7201 8566 1077 7361 8657 8997 999 3194 503 1705 3764 9184 542 4036 5100 7432 2051 7110 4596 7244 245 5856 3571 5689 3514 8304 102 9874 2782 7807 641 3703 1014 5198 593 5011 7955 9516 4303 8354 12 1099 6098 6920 7030 8966 1720 7445 2468 8134 2771 4989 1537 4817 2919 5086 3653 6423 407 621 5823 7140 7209 8705 1856 8526 7765 9371 913 952 5448 6049 4694 7356 629 8595 610 9429 7216 9151 572 3360 7775 9677 3938 95…
Output: 6057

Example 2:

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

Example 3:

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

Constraints:

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

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