CT35194

Bhavi's signals Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the ribbon falls of Cascade Vale pays by the answer, and Bhavi intends to earn it. First: the full register of signals. 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: 4000 3765 816 2129 3337 3425 1753 2094 761 3552 529 3128 779 1985 1486 3333 3325 3823 2526 3488 5 2129 220 2162 2703 3634 1425 2057 1445 3053 2619 3753 2978 3982 1797 3747 364 1109 865 2035 1093 1917 2757 3240 2121 2755 3245 3813 49 1119 182 2781 2313 2371 2545 3649 1505 3644 592 2009 823 2478 458 1745 1230 2099 1270 2032 638 743 1646 1920 2371 3635 780 3184 231 3680 1115 3010 2079 3301 86 3936 80 2461 1386 2640 215 3258 1586 2036 1747 3810 144 1981 578 3658 1459 3930 2508 3493 1235 1710 161 511 341 3044 381 1960 685 1614 2408 3695 29 2596 1716 1820 880 2462 3699 3961 216 2714 1352 1987 1445 3422 494 3909 2314 2957 833 2451 381 1792 2198 3031 958 3081 1037 2806 1789 2948 2021 2482 1517 2922 1005 1468 694 3964 1292 1352 1713 3418 2254 2489 412 2189 2621 3733 948 1287 449 469 2741 3702 211 1…
Output: 732

Example 2:

Input: 2 1 1 2
Output: 0

Example 3:

Input: 10000 3761 1133 3532 2391 9684 6034 8770 4227 4922 234 3012 3705 8061 7031 7400 8238 8997 1357 8124 283 2648 3579 8975 4687 7761 2749 3666 1516 8438 837 8279 1268 2409 409 4244 2055 8860 5042 8314 4625 6115 320 2764 243 9189 7386 7559 5891 8105 4383 6102 1086 2997 4295 4596 4505 7338 2676 4828 2092 2999 4650 9884 4386 4547 7380 8610 3116 8843 4778 9105 4433 8172 4273 6080 2695 5459 2289 8056 5692 7119 1691 2390 7697 8723 686 7299 3908 4037 3008 7716 2740 4677 4246 9565 7350 7656 2401 2516 1425 2059 9007 9617 5855 7263 2034 6021 4021 6581 1286 8600 7969 9847 3625 7735 5901 8889 4834 8665 7441 8640 7335 8190 1087 9634 350 5757 2959 9952 7583 8842 3279 5988 2547 9231 5105 7271 1173 8612 519 6073 4761 6343 3712 7897 731 5007 7278 8436 788 5869 1338 3325 1253 6871 1084 2885 2748 9545 2016 3007 …
Output: 6238

Constraints:

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

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