CT55732

Bram and the Link Budget

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the railway depot of Cinderline, someone must catalog the new acquisitions. This year the task falls to Bram, armed only with the registers register. 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: 2 1 1 2
Output: 0

Example 3:

Input: 4000 1807 2291 2327 1020 1941 1339 3274 144 3380 357 1926 909 1371 414 3263 2561 3895 1763 2485 1050 1474 2675 3848 169 265 1194 2534 1998 3766 13 1804 1646 3057 584 1407 43 2878 1336 3472 89 784 825 1912 1113 2686 1372 2033 314 1147 105 3185 569 3223 202 648 1672 3357 3365 3848 789 1883 1988 2880 72 2637 2637 2747 65 2614 434 3906 421 1464 536 1255 3056 3386 851 1869 662 3540 979 3041 1417 3739 936 3785 2129 3892 59 1113 1089 1549 323 806 366 2696 635 2859 473 3810 1042 3427 603 1609 436 2555 1813 2750 136 2925 410 2435 2675 3762 2342 2660 846 3098 977 3997 2271 2662 2352 3113 1257 3202 506 2850 580 1279 3367 3477 955 3009 493 1739 2620 3964 2215 2364 411 3736 2419 3169 2674 3928 1200 2628 322 3081 2886 3735 1393 2973 626 3917 2537 2572 3345 3797 3051 3236 2693 3788 1723 2181 568 1316 161…
Output: 2193

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Bram and the Link Budget - MEDIUM Coding Problem | CodeTikki