CT52196

The Link Budget of Crosswater

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Faye inherited the stall at the ferry landing of Crosswater along with its curious bookkeeping system for ledgers. Time to make sense of it. 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 1428 5327 9000 7239 8798 1818 4675 1147 6491 1464 3449 4087 8042 756 7070 1775 6542 4868 9991 4572 8132 1613 3376 7300 9087 1736 5114 5144 9152 271 3123 1916 7990 5927 6405 1946 2344 1826 5837 3316 8298 2074 8339 3489 5037 5996 6085 6119 9650 2379 7570 7859 8547 2312 4746 861 3976 5893 8848 2240 6550 3030 7884 1568 5274 2223 6647 78 7913 1728 4334 5667 8258 2989 7571 6415 8886 2003 4973 521 8597 1381 2471 1726 2702 1501 5260 1891 9416 561 8054 2455 3722 3200 3835 2736 3646 6895 8542 1642 3540 2225 3251 3175 9780 3953 6619 1580 1603 3186 7768 3879 4395 4759 7206 1198 5675 4598 4609 7581 7776 1225 4076 4507 5837 3321 8237 3790 8120 4891 5532 6922 7385 1129 3659 6916 7766 3555 4398 2325 7504 2141 9999 6914 8005 2644 5885 2615 3123 6129 8016 2525 9527 1928 8987 1131 7074 4321 8638 2256 3…
Output: 8571

Example 2:

Input: 10000 1616 8975 9518 5759 6346 1292 3368 2160 8156 5190 9276 724 4399 242 944 1267 7891 718 5156 3330 4064 36 9821 4093 6247 686 6205 4704 9502 85 8356 5804 9832 6071 8643 139 6858 447 9011 5974 9837 443 8998 1770 8172 345 2896 2737 6506 3179 8916 2815 8836 3444 5164 5805 6690 2004 5898 602 982 6351 6891 824 8290 726 3762 775 3992 5057 8217 69 7985 1474 6801 2427 8893 5266 5296 7290 8898 4885 8406 3819 6912 4984 9388 9458 9629 1805 7106 2266 7042 4969 8897 6574 7836 1032 2288 154 7189 5620 9615 4023 7377 6702 6966 3150 7822 2173 6870 4434 9678 4384 9114 174 7534 13 6554 7497 9033 1696 3169 288 9801 1212 1851 3159 9666 3344 3547 5333 9160 3264 9942 2504 3344 1684 9533 2094 2166 5700 9549 6625 7422 6930 8002 332 3086 1155 1791 42 1203 3328 9906 6515 7973 1639 4328 400 420 4464 7425 3546 6939…
Output: 8383

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 Crosswater - MEDIUM Coding Problem | CodeTikki