CT40247

The Sunlit Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Surveyor found an old ledger of beacons in the apiary attic at the windmill fields of Gusthaven. The margin notes pose a precise question. 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 3785 1748 9507 6969 8802 356 8901 727 4846 7709 9018 5892 8444 6145 6814 7703 7975 1619 9570 6014 9889 1200 4342 8279 9118 2842 7210 3552 9237 502 4287 2789 5182 3181 5962 6304 8096 1496 5100 2645 3738 1504 5841 3782 6094 220 8593 3243 5480 656 4084 4071 7576 506 8836 7750 8738 3347 9800 3861 3888 6541 9231 4321 5602 768 5521 1179 2707 589 4587 811 3595 2035 5149 3521 8201 439 8063 1613 9270 2438 7003 395 7348 1275 4076 4547 8808 2242 6622 8188 9428 770 9203 4744 9190 1727 7670 3324 4878 2107 7787 6736 7843 6862 8806 2579 5664 8683 8705 4060 8637 8177 9335 3774 6463 1209 2574 3915 8935 152 7920 1126 3002 3160 8398 2123 6269 1491 4615 4263 8708 4918 8478 2414 7404 5259 7002 244 1448 758 1584 5294 5664 81 6713 1578 4150 2747 8633 2257 9394 568 2613 1354 2316 7077 8923 3793 3850 8302 94…
Output: 6214

Example 2:

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

Example 3:

Input: 2 1 1 2
Output: 0

Constraints:

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

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