CT40694

The Link Budget of Misthollow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the valley of Misthollow, Admiral studies rows of ledgers 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: 2 1 1 2
Output: 0

Example 2:

Input: 10000 1023 1439 7400 357 4796 2121 8869 768 5332 3040 4396 1977 9841 1560 9860 8481 8529 5573 9528 5309 9914 1174 1837 2132 3460 5776 8798 5292 7212 2572 7972 1767 8567 1398 3228 6225 8025 1454 7129 773 7554 1018 1372 3587 6668 2965 6143 2643 7209 4056 6384 1537 3355 1440 2087 679 2473 271 1373 6124 7758 6299 7299 2450 4950 2398 5668 1997 3826 4027 6074 2427 7517 7504 8681 5035 6949 1450 7478 7426 7694 989 8471 799 8099 3991 9663 1434 7257 6133 9835 4897 5961 347 8982 2094 5914 1703 8794 6621 9282 5597 6677 5689 7617 1680 4972 1410 1807 4947 7656 2490 7081 817 3825 4452 8133 4771 9757 3044 5467 1517 8822 909 7234 1816 4601 2039 5114 7020 8230 1448 8357 3842 9226 3604 8811 4278 4397 4393 7277 1017 5585 3614 4479 1013 9436 6611 8352 5429 6186 3819 9195 4781 5620 1302 1789 1219 1332 541 6480 …
Output: 8976

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.
The Link Budget of Misthollow - MEDIUM Coding Problem | CodeTikki