CT52685

The Pale beacons of Sailor

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the opal reefs of Shimmerdeep pays by the answer, and Sailor intends to earn it. First: the full register of beacons. 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 12 4 8 6 10 6 8 4 9 2 6 3 10 7 9 3 9 3 8 3 7 5 9 2 3
Output: 1

Example 2:

Input: 10000 1109 1348 6270 5231 9653 1535 3711 3987 5756 278 6175 4644 6976 2261 5707 2797 5074 5969 6022 331 2841 2644 7888 1987 9312 4680 7779 497 8940 6134 7035 2904 7196 586 3481 1430 6900 4257 8481 123 3453 1250 4402 5040 8672 7850 8902 5315 8475 392 5112 608 3349 1909 8960 5912 9544 7535 8735 3328 3524 7385 7950 1657 4903 4982 8488 6065 7032 4005 6377 5211 8185 17 2246 2942 9813 2063 7036 3396 4353 3415 4377 201 5030 782 5535 4528 8363 4328 5339 3193 4928 2753 3177 187 9860 3444 4372 4223 9000 6592 8658 4185 9174 4447 6155 2365 6794 978 1518 445 9128 19 3329 7640 8753 4690 5429 714 3231 2328 5409 5958 8024 1028 4750 1187 2120 1680 5095 3759 9179 8094 9142 7962 9345 2792 7938 4426 8402 7844 8148 892 8161 1510 7265 4110 9167 2940 7264 3661 8461 5008 6534 4528 7023 3058 7671 617 8404 897 7085…
Output: 8890

Example 3:

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

Constraints:

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

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