CT36482

Tara's Link Budget Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the gristmill of Rye Hollow. Tara spreads the signals 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: 4000 242 698 2493 644 3843 783 2277 1032 2780 1374 1592 2437 2742 747 3163 109 1910 2928 3892 1436 1655 2089 2545 80 3937 817 3272 420 3648 2512 3302 422 2214 241 400 1160 2487 414 3479 379 3524 1319 3672 1077 3279 1544 1981 746 3301 1095 1325 2302 3947 567 1423 463 1912 1718 1974 2977 3126 1653 2884 2231 3071 3393 3587 517 2792 1687 2991 1938 3693 1952 1984 1159 2536 861 2690 984 2831 115 3592 454 688 1833 3093 1582 3224 3074 3987 2531 2650 1428 1896 881 3568 252 1299 270 410 3458 3924 1329 3698 644 1220 1565 2871 1666 3044 1160 2929 680 796 2158 3425 866 2529 68 2619 1727 3427 109 3382 1477 2158 1991 3675 229 3793 120 2792 1622 3237 427 3095 83 535 1729 2951 1943 2139 918 3355 259 3029 49 2736 978 1298 2005 2957 493 3394 2058 3181 1817 2006 511 1339 487 1710 1020 2643 1207 1451 1178 3030…
Output: 3757

Example 2:

Input: 10000 155 3131 8745 2363 5083 2964 8487 296 3483 2386 9615 1126 3933 1674 9239 5761 7160 3587 9477 4798 5044 4482 4726 1914 2826 6062 8714 3799 4757 1084 2795 5058 7125 6341 8549 1440 9376 1114 3365 1770 4744 2368 9995 3327 5186 2996 8505 5855 6948 4710 5469 8059 9807 8635 9726 3077 7837 2191 4330 4720 8249 3158 4879 2358 7341 6994 9126 753 8369 4276 4782 4850 5912 469 5597 6888 9536 2239 2869 1578 5113 6186 9262 4454 9153 1998 7768 4793 4859 4032 9795 4865 8197 6905 7351 1224 2481 1576 2382 2437 9213 4222 7101 4491 9605 6682 7031 1960 3785 6699 7286 3233 6068 6924 9099 4084 7246 1300 8911 3419 9671 814 5490 3667 4679 1088 4506 5601 8104 4529 4719 4159 7400 886 3298 3474 9259 408 6652 2301 8505 2875 5434 497 1083 9081 9493 2910 7423 9400 9474 8417 9632 393 1343 271 5279 1718 1841 1691 7831…
Output: 9844

Example 3:

Input: 2 1 1 2
Output: 0

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Tara's Link Budget Ledger - MEDIUM Coding Problem | CodeTikki