CT41201

The Firewatch Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the caldera rim of Firewatch. Quin spreads the beacons records across the table and picks up a sharp pencil. 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: 2 0
Output: 1

Example 2:

Input: 4000 1556 1504 3594 836 3908 2031 3706 1399 3420 1367 2252 512 2848 1434 1735 1345 2624 1256 2002 1534 2927 865 3682 2558 3704 3020 3756 2406 3996 2277 2465 2123 2869 1685 2136 2133 2309 821 2898 1076 3854 646 1087 1771 1961 193 3569 1151 1308 3273 3760 1175 2375 3450 3697 657 1789 412 3317 695 945 755 2111 2015 2902 2285 3173 323 1277 197 2618 36 213 1896 3422 1793 3627 1686 2527 1706 3484 2428 3412 1568 2847 134 2844 1825 2228 1261 1357 1955 3523 814 1655 1371 2597 523 2858 227 598 498 3707 2013 2267 1383 3806 2061 3658 834 1426 1940 2926 3082 3843 268 2228 2419 2771 2888 3226 570 754 209 1590 2809 3038 2044 2414 1478 1583 306 1153 125 2080 839 1309 227 2905 2254 3758 1264 1299 63 3852 1454 3481 2344 2700 206 1517 1253 3559 524 2980 448 1768 2309 3543 2717 3861 218 1263 1208 2302 99 1904…
Output: 2444

Example 3:

Input: 10000 3880 2251 7773 4612 6803 4836 7810 2709 5765 291 1633 5773 5779 139 6677 3852 4109 4465 9532 1255 9304 4022 9771 2269 9200 1970 8032 5461 6957 1000 8938 2488 4375 965 1341 5093 5748 1049 3481 6303 6783 2715 7305 3677 6523 5624 8152 1951 9276 6218 6488 237 4092 530 9665 541 5529 3152 3647 38 1918 4009 5537 1394 7665 3360 4075 1978 4439 4751 5224 721 6018 145 3504 5752 6650 2279 5312 6708 7582 541 8327 347 6568 7036 8851 2227 8063 2095 6752 2552 4174 5149 6207 2009 7141 5714 6824 7238 9827 4649 7798 7578 9174 2837 7579 2037 6079 5618 6172 4449 5733 8261 9738 5955 9920 1779 9630 9517 9918 5567 7375 6944 9679 2224 4510 1527 7510 930 5936 6223 9953 1950 8612 3055 7484 3377 6742 4088 7171 2854 5742 4443 8027 7339 8710 8028 9603 494 4915 2015 9747 4999 7725 7385 9222 6281 6468 4222 7623 220…
Output: 6119

Constraints:

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

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