CT35372

The Vermilion Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Gautam runs the signal tower at the ivy courts of Vineward. Today the books show a list of signals, and the numbers must be worked out before sundown. 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 1458 1071 3995 2946 8036 4868 6477 1669 1890 5921 7983 2700 5380 6892 7379 4219 9805 8229 8738 150 4739 6379 9445 1056 4899 4789 8908 3532 9981 5885 8185 6516 9132 2013 9442 1264 4240 2003 5211 1385 4218 3009 7887 974 7255 2495 7776 3681 8015 4792 8488 1226 6266 1934 2820 1346 8663 5479 6512 5492 6713 5528 9438 3561 9373 460 4909 4377 9923 7070 7344 3719 5603 1964 9754 3376 9742 1207 6948 6238 9423 307 4862 42 9971 4476 9065 5489 5634 91 1017 3868 5029 8051 9587 3024 7657 117 2690 2425 4531 2333 9836 361 9193 4005 9217 1949 2704 1168 3136 1196 8322 3817 5305 1432 1979 7100 8869 2372 4616 1413 5689 1212 3688 5404 7984 7483 7524 2664 5885 1388 2071 2406 5375 412 7988 6585 9143 1440 8392 2263 8853 227 3367 897 7277 5240 5351 3200 5075 1269 1656 5302 7863 5573 5944 3354 6664 3712 8836 46…
Output: 8541

Example 2:

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

Example 3:

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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Vermilion Link Budget - MEDIUM Coding Problem | CodeTikki