CT40565

Innkeeper's registers Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the northern keep of Frostgate, Innkeeper the customs officer keeps careful count of the registers. Document the rare sighting, every figure matters. 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 2964 18 90 32 84 44 66 3 92 32 74 65 84 28 68 4 65 8 34 57 72 52 72 73 80 92 100 32 97 54 78 24 99 20 41 36 51 7 56 69 96 21 38 51 53 6 74 4 51 4 64 36 49 40 80 88 91 44 76 48 83 78 81 48 90 39 88 14 49 75 93 19 80 78 89 15 53 20 58 69 77 18 63 29 74 9 84 33 41 42 66 4 19 83 91 67 91 5 67 2 75 51 70 24 80 9 80 39 57 27 30 26 54 58 73 55 85 54 88 21 98 7 67 27 56 2 96 14 15 9 37 8 90 44 81 65 86 1 57 31 45 25 77 37 71 37 76 33 97 17 63 77 99 39 79 93 94 14 57 17 39 7 58 49 63 63 71 51 61 20 89 18 30 51 76 7 8 79 90 24 30 24 60 77 83 57 99 11 94 11 77 40 95 14 68 18 51 28 89 48 94 21 80 32 72 2 95 60 84 23 68 69 86 26 89 43 65 34 40 14 54 30 31 24 42 16 32 1 90 75 80 8 55 43 53 3 82 62 83 19 38 14 18 14 43 21 47 23 66 9 73 10 51 53 57 54 95 49 86 70 100 22 67 33 48 84 86 20 78 21 73 69 9…
Output: 0

Example 2:

Input: 10000 1356 2858 8723 8145 9035 1505 3530 3390 4826 3405 4315 3384 5800 1861 9513 2797 4568 4568 8452 431 7070 1400 1572 7758 8928 2085 6820 596 3455 22 4590 5127 8131 1166 3644 1127 9984 4043 5032 4428 6811 5561 9040 812 1857 2669 2848 2148 6439 5984 9281 1394 5180 1813 2283 4316 5992 832 4904 459 5561 3860 4361 1148 3504 329 6273 4664 7192 393 9006 162 6540 3955 9526 6731 9461 1485 8292 6230 7299 8484 8747 258 7798 6352 7498 1503 2918 5166 9603 6637 8032 2069 6991 1456 1964 3231 5685 991 5697 4248 4448 7501 9457 2371 5564 3718 9636 1218 9678 576 5254 3440 7073 4467 5951 1213 7754 106 5905 2619 2653 1067 7318 7493 7915 309 999 5631 6763 3350 5601 1232 8454 699 2128 3600 4631 566 4466 2981 5322 5491 5840 256 9198 5609 6178 574 9925 7323 8101 6032 6881 2462 7293 4054 9652 1219 4468 5649 9397…
Output: 8643

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Innkeeper's registers Reckoning - MEDIUM Coding Problem | CodeTikki