CT53097

The Brass registers of Gita

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the quays of Driftwood opens only for a perfect tally of registers. Gita means to find out. 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: 10 40 1 8 2 4 3 9 7 10 9 10 7 8 2 10 1 5 3 10 5 10 5 7 3 5 2 9 6 8 5 8 2 6 1 6 3 7 8 9 6 7 3 4 6 10 1 7 2 3 4 8 4 10 3 6 4 5 1 9 8 10 2 5 1 10 1 2 7 9 2 7 1 3 5 6 4 7 3 8 4 6
Output: 0

Example 2:

Input: 2 1 1 2
Output: 0

Example 3:

Input: 10000 2184 5891 7422 2122 4747 1020 6490 1286 2323 3153 7055 4040 8172 1597 5684 5801 7245 2705 2961 7922 9343 2358 6333 9413 9442 3927 9951 260 3822 3795 4226 5908 9041 6530 8496 401 3462 2198 9855 2185 8035 8102 9762 4588 5349 2171 7648 1086 4651 934 5462 5857 6954 3393 5015 3900 8976 656 5271 6164 6758 7766 9273 8556 9330 3073 9488 3880 6444 4370 7019 2444 5825 6598 6905 935 9767 1146 6794 2834 7355 6661 7210 4318 6525 680 1266 56 3330 4565 9267 178 9602 3841 7830 41 7925 1827 8088 3105 3951 1100 5555 7139 8043 2985 9671 1319 9116 87 2008 8493 9693 1918 5537 2228 2529 2714 5167 6998 8438 456 6836 712 1527 557 2994 3333 5451 338 7230 1236 7287 8631 9356 7506 9536 3355 5317 257 7594 1182 8506 1895 5995 8566 9961 4100 6714 1778 1882 2376 2501 1021 8033 28 5182 4991 8560 895 4539 3125 7610 …
Output: 7815

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Brass registers of Gita - MEDIUM Coding Problem | CodeTikki