CT49765

The Link Budget of Brasshaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the old quarter of Brasshaven, someone must settle the inheritance fairly. This year the task falls to Zephyr, armed only with the signals register. 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 2804 318 6190 104 1290 1955 9806 1826 6313 1627 7223 3206 7877 1363 8388 1295 2286 1606 2335 9428 9711 4490 4912 1478 8734 6093 6508 934 7564 3994 9354 2207 3527 5564 7537 1205 2885 12 9447 5522 9549 1997 7668 4741 8767 7455 8519 809 7546 3060 7774 9025 9842 1632 6494 7682 9164 6963 7987 2422 3228 6254 7789 1758 9685 3793 8506 7668 9470 7652 9465 8784 9656 3066 6377 6425 7860 7295 9185 2863 6257 7087 7237 1668 8299 4202 6438 1534 7921 2696 7807 767 6744 2219 7430 1777 2998 537 8534 253 3462 5086 5351 9098 9883 6339 9254 60 7999 4138 7568 2234 3767 9608 9990 3117 6153 3808 7309 2694 3641 790 7322 3033 8872 3817 4702 5612 6877 3184 5866 2889 7830 8408 9431 8583 8960 4095 6257 4843 8722 826 3518 135 2091 315 3115 2315 3074 5119 6721 4064 9543 430 8503 6566 6817 4744 7025 6030 9176 206 7…
Output: 7195

Example 2:

Input: 10000 3638 2918 2991 7983 9300 2608 8821 2878 3684 847 6914 1462 9724 3982 4020 7128 9267 3209 5845 1136 4224 7539 9468 178 6653 770 5858 2020 7339 2103 2488 2558 7021 1053 3481 5428 9873 5410 7429 1589 3900 8458 8887 429 7885 5765 9661 3872 9081 1603 6137 993 7518 1911 3459 4749 9707 951 1151 6607 9387 7536 9104 3439 6192 793 3120 7702 9171 2988 9116 3494 3949 2572 8302 2340 6518 4733 7982 38 625 3188 5847 2184 8701 2183 4334 4109 5215 5317 7135 1361 5340 7627 8536 4418 5698 8255 9801 127 7034 3898 6292 5695 9829 4745 6039 1176 9509 907 6069 643 9689 3233 7836 3503 3810 5908 7110 334 4000 5131 6812 2191 9730 327 7649 2019 6273 6801 9938 5645 8744 6206 7591 6451 6539 6594 9175 7662 9760 5695 7357 292 4605 8257 9392 8475 9335 3886 4097 3079 7761 8681 9742 3591 9669 4080 8744 5929 6977 872 6…
Output: 6361

Example 3:

Input: 2 0
Output: 1

Constraints:

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

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