CT36962

The Rootwater Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The quartermaster Herald has been asked to optimize the storeroom layout. On the desk lies a long table of marks readings. 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: 10 22 6 9 8 10 1 5 2 8 7 9 2 10 8 9 1 2 3 7 3 9 2 3 4 5 4 10 7 10 3 8 1 3 1 8 5 8 3 6 6 8 1 4 5 7
Output: 0

Example 2:

Input: 4000 250 2330 2880 1030 1177 2662 3097 2432 2457 3268 3435 2192 2441 971 1146 816 2416 1002 3088 2448 2803 667 3713 2162 2599 1503 3789 885 1034 152 329 334 1292 921 3869 523 3650 2246 2595 1165 3607 1089 3125 99 993 52 360 3049 3413 2163 3261 1350 2058 816 3407 1070 3784 3564 3576 1777 3278 160 3729 758 1321 3319 3713 333 3035 60 357 706 998 3066 3971 1018 2657 836 3998 1752 2949 963 2806 195 2952 1866 3717 840 3450 3414 3872 1057 3585 77 1000 3012 3569 737 1032 1424 2606 1026 1497 62 2814 58 3850 407 3670 2264 3107 497 3095 3436 3513 616 3690 306 2812 1116 1517 1786 3073 1192 3442 2009 3369 880 3816 2655 2703 543 3152 138 306 479 3455 848 1062 696 1641 1810 2803 295 2820 843 3266 893 2654 630 3395 2429 3685 264 303 3334 3899 3372 3472 1081 3319 754 3436 1606 3479 1470 2065 2210 3727 481 …
Output: 3749

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Rootwater Link Budget - MEDIUM Coding Problem | CodeTikki