CT39463

Last marks of Esha

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the monsoon port of Rainhaven. Esha spreads the marks 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: 10000 2641 6953 9186 1283 8120 714 7048 4555 7314 2436 5499 782 4867 4064 6085 3015 8213 1085 2320 2379 6181 3821 6480 6579 8546 6042 6811 1404 9813 964 3289 5288 6506 3640 9421 775 2985 7814 7920 5953 6445 6196 6721 8617 9725 2128 8703 6437 8093 3252 8557 7636 9645 630 6383 3097 9823 3122 8028 449 4149 2519 6255 602 9424 2106 8833 676 3942 1675 7744 1730 6034 3480 7025 2047 2754 7044 8727 1876 3850 4830 7732 8144 8225 7136 7352 4633 4751 3748 9812 1587 7156 87 4180 1867 9770 3972 7391 4430 7116 5939 7106 4003 7310 9150 9618 8449 9939 869 3134 2873 9541 1048 4596 1248 6193 2446 6067 7008 8803 3371 8935 7254 9574 1971 9754 6892 7718 1152 1395 1787 7172 948 6099 4333 6121 6856 7550 2275 9104 4051 6325 5585 6353 941 8559 7713 9833 2298 3752 857 2442 6193 6526 5197 9136 3522 3837 6229 8851 464…
Output: 7358

Example 2:

Input: 2 0
Output: 1

Example 3:

Input: 10000 3859 5867 9775 4868 7005 920 1613 3264 5500 2633 3103 3858 6919 4473 6889 460 7770 2783 7135 2218 8218 4194 4519 5421 7175 2201 7327 1436 4966 4443 8536 4796 5466 4024 7913 1390 6037 3093 6680 3097 8506 113 3062 4042 7626 7353 8929 2385 4621 1311 3653 7183 9647 6849 8835 9324 9726 314 8888 1784 3736 2926 6296 1216 1260 2518 3730 174 3076 4013 6801 1275 7644 6939 9885 4036 7989 5280 6468 154 2840 5228 5976 4522 7584 3394 5297 6104 7297 4635 5475 8937 9604 2973 9559 436 9503 685 778 3710 9504 4247 4976 3379 5157 771 6378 1961 7101 4542 6275 4074 7635 4093 4626 4671 9729 207 7300 2027 9489 5509 6386 1688 1806 4297 7562 6355 7795 5569 6020 1143 9044 5237 5584 6588 7400 7833 7978 2994 7719 6519 8419 6263 6696 9248 9973 2584 8523 3973 9808 4548 5165 178 9524 1385 3799 8313 8658 3778 4903 5…
Output: 6140

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last marks of Esha - MEDIUM Coding Problem | CodeTikki