CT47300

Last marks of Librarian

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the salt flats of Palemere, Librarian records each marks in a worn leather ledger. The guild wants answers, not guesses. 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 3247 4714 6442 587 727 1775 5068 1012 8435 4488 5478 994 8284 1612 2567 1432 7604 2065 6945 4640 4913 1693 2590 7737 8780 197 7176 362 6069 3861 6009 6476 8471 7858 8550 2100 4806 8290 8334 1294 6943 647 4221 2962 9447 5356 7987 2547 7720 474 8025 3303 6208 727 4901 708 4463 593 5473 4480 4728 1978 3692 2978 6004 2326 5034 9950 9961 4151 7145 39 1280 144 1820 1036 7838 597 6831 761 9882 1353 7245 3960 5561 3890 5301 2807 9735 2091 6865 8001 8786 1014 8792 6899 9418 3859 9421 40 6383 4081 4794 1159 2958 58 4109 4031 6695 2127 5508 3945 8010 5913 6920 1860 2229 6291 8879 5037 5346 5693 8458 6588 8396 5920 7962 135 4562 1553 8472 6384 8736 7021 7217 634 1665 3061 9321 7899 8514 4665 7442 328 6079 2531 6679 2548 6836 3277 3564 661 7734 2559 4845 3876 7319 6550 8535 2987 7021 3509 8957 70…
Output: 6752

Example 2:

Input: 10000 305 420 8617 3471 3725 3025 7765 256 8381 2128 5271 736 3262 3859 9811 4700 9401 5517 8926 3519 4562 2509 3569 8092 9439 1724 3000 361 8762 8727 9699 4748 5666 2441 2816 3817 8356 1661 7277 1720 1856 3823 9529 212 3783 7847 9384 895 1300 2025 3837 1566 3425 1813 3024 3090 5658 7688 8356 2005 3887 1675 3190 3989 6595 2401 4298 2665 7444 3247 3554 4009 9425 3847 8907 4888 5738 3096 4395 8709 9769 1460 3135 1643 4613 1070 8574 961 6636 923 6847 2101 8750 2026 2343 3528 5266 616 3741 600 6970 1662 8428 3358 4371 2326 2335 4504 5286 489 5535 1230 8443 3520 4015 5290 6082 2831 6814 5585 8972 396 3797 505 7671 123 8325 4464 8061 5936 8405 892 3850 5954 9205 2191 7361 3416 7110 4221 9568 137 4143 2055 5299 2302 6482 2416 5883 8017 9603 2131 6990 1093 4195 758 2672 7473 8533 460 7764 17 4613 …
Output: 9694

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last marks of Librarian - MEDIUM Coding Problem | CodeTikki