CT53563

Vigo and the Teal ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the basalt cliffs of Obsidian Shore, Vigo 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 0
Output: 1

Example 2:

Input: 10000 3848 7662 9342 4091 4435 2245 7010 1597 2711 2291 8283 2674 3154 4066 8163 3840 8180 3369 9636 4537 6838 4037 9053 8156 8569 6891 7787 4136 4259 5265 7072 4287 7240 3432 6404 4725 7377 4144 5409 2634 2885 5650 7533 207 4311 316 9221 1927 4396 3691 8589 7085 8317 2434 7537 5177 8400 2414 9842 1541 7519 5389 9557 1849 3101 6417 9586 3971 8624 127 7504 3142 8196 4044 9794 4206 8339 4031 8970 4411 5956 975 5317 3620 3802 4632 7272 2146 7388 3024 6445 2800 7848 3278 6921 2854 5570 2070 6783 7066 7520 1538 3044 697 8010 2790 9219 5441 7495 1789 1993 1645 6525 1256 6973 653 9492 811 3297 4786 8606 686 2521 2769 9041 6614 8825 119 4000 4092 4328 3891 9718 4133 9565 947 9661 6175 8270 3288 7178 3601 6186 4560 5169 5000 5468 3680 6472 2317 5367 3657 8238 2944 9104 1676 5733 6212 8784 152 1606 …
Output: 6151

Example 3:

Input: 10 10 5 6 7 10 8 9 4 10 7 8 9 10 2 7 3 4 4 6 2 4
Output: 1

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Vigo and the Teal ledgers - MEDIUM Coding Problem | CodeTikki