CT47935

Jaya's registers Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the desert outpost of Sandspire, Jaya studies rows of registers entries. One clean number will settle the guild's oldest argument. 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 2395 1545 2825 2165 2183 323 630 2020 3461 1367 1874 894 2760 1892 2961 139 2319 46 3077 1692 3082 2156 2305 712 2099 103 1739 3749 3957 2227 3819 1436 1785 1619 3002 207 1140 1303 2427 477 2929 549 2664 1974 3194 195 3642 299 3318 466 1536 648 3221 1253 2090 722 3216 400 1883 1784 3356 927 3711 3697 3737 212 2108 1058 1437 1715 2147 1787 2981 479 3143 1114 2040 1410 2698 2917 3424 2472 3462 1359 2182 1363 2648 721 3463 2533 3915 2086 2255 324 2385 773 1487 3714 3978 1735 2179 635 1507 1722 2338 125 3986 774 890 3024 3098 1701 1941 1163 3943 1162 3103 2722 3953 42 926 391 3090 1679 1763 2404 3276 1130 3427 1456 1489 737 3300 909 2578 503 2049 948 1590 27 3492 1701 2949 1442 2980 997 3691 1550 2611 1317 3562 249 736 1892 3567 123 2904 136 2001 1178 1913 622 2300 151 3461 3667 3707 634 …
Output: 1612

Example 2:

Input: 2 1 1 2
Output: 0

Example 3:

Input: 10 4 4 8 3 9 3 8 3 5
Output: 5

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Jaya's registers Reckoning - MEDIUM Coding Problem | CodeTikki