CT49708

Tracker's ledgers Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The clerk Tracker has been asked to rebuild the damaged itinerary. On the desk lies a long table of ledgers readings. 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 35 1 8 5 9 4 9 3 6 6 9 3 4 2 7 8 10 4 10 5 8 2 8 3 9 1 3 1 6 1 5 1 7 2 6 8 9 2 5 3 5 1 9 3 7 1 10 4 6 2 9 7 9 4 5 1 4 2 4 2 10 4 8 5 10 4 7 3 8 6 7
Output: 0

Example 2:

Input: 2 0
Output: 1

Example 3:

Input: 10000 1285 1100 9490 6058 9300 1147 6090 8028 8927 4080 5499 3186 7922 676 7057 4095 9879 2990 4338 3281 8176 3099 6392 4139 4943 2803 3923 1465 7147 1022 6111 1814 8331 3474 6857 72 2836 1302 7713 5280 7001 6505 9313 2637 5316 1541 4747 6114 9589 1165 8573 1637 4615 2995 7253 241 8571 945 9079 2021 2627 1499 6743 3970 4805 5745 7539 6736 9751 1650 4217 1332 8639 361 5282 7364 8385 1505 2236 6117 9389 5788 7336 437 6695 2926 2984 2725 4394 6376 9992 6860 9007 13 7868 1018 9668 867 3028 2915 7097 6589 9070 155 9935 6995 8813 2909 8987 3794 4576 5982 6825 649 7674 2528 4398 4434 9169 5147 6917 1458 8557 5309 8707 5302 6191 3851 8275 91 7886 4083 8948 2399 8815 1283 3909 6021 7697 4728 5401 3258 5383 545 6302 2453 5125 7496 8517 1851 4244 3602 4102 5392 7274 1117 3056 3643 5162 1883 6297 3152…
Output: 8714

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.