CT37780

The Wistful beacons of Ulrica

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ulrica the log keeper watches over the seal rocks of Barking Cove's stores of beacons. A careful computation stands between order and chaos. 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: 100 1902 31 54 11 54 47 78 17 83 32 71 36 77 34 49 41 71 10 85 61 94 8 55 67 70 23 77 2 58 14 41 35 100 20 76 44 97 90 95 19 88 9 59 1 53 31 43 12 17 3 46 48 59 19 66 8 49 26 81 19 53 4 38 20 63 82 96 11 35 24 73 53 71 17 41 5 85 15 16 34 76 27 82 52 99 85 90 17 19 50 83 7 12 84 99 3 85 11 60 42 63 89 96 7 73 63 97 9 10 24 89 43 60 38 55 20 35 9 65 2 82 8 96 6 95 65 67 21 48 45 55 78 91 10 29 87 89 52 78 24 100 11 49 10 30 23 33 14 52 33 60 35 67 87 99 85 98 39 71 1 67 29 65 3 81 40 55 29 77 4 53 5 63 15 99 91 100 60 68 66 91 8 31 2 64 11 75 40 92 25 68 80 86 4 22 9 16 71 75 53 62 51 90 25 77 27 68 13 33 33 84 8 40 20 97 49 63 12 35 6 53 11 27 8 17 30 42 14 78 47 71 6 97 49 87 21 65 11 53 71 88 32 75 8 79 26 72 23 48 40 46 15 60 37 70 45 83 2 28 13 38 7 84 36 60 59 97 13 15 63 94 63 88 75 …
Output: 0

Example 2:

Input: 4000 835 1986 2133 1191 2637 2461 3117 1470 2114 3281 3499 1269 3107 605 1664 1037 2536 1350 2057 1956 2347 424 1607 1003 3031 769 3350 1832 3963 15 2274 1353 1573 109 1140 1206 3672 1931 2238 2240 3435 839 3725 627 3427 258 2545 893 3225 658 2001 2717 3186 751 3962 1722 1858 103 3609 2697 3864 1408 2552 2403 2974 2200 3139 1491 2166 663 669 639 3020 2172 3612 2103 2304 2544 2826 1698 2998 1074 1262 825 1850 483 3027 2764 2982 2114 2435 2058 3692 799 2325 2665 3705 740 2042 16 3686 2987 3523 702 1063 710 3140 3018 3931 1027 1831 100 3601 1224 1542 526 2980 3836 3949 298 3604 2277 3467 1899 2141 3038 3579 1159 3814 1233 2185 1921 2450 1487 1886 431 1493 3063 3145 1209 2617 839 3912 102 131 1126 2164 2826 3544 619 2052 312 2664 276 3891 203 3080 664 1369 2716 3217 2614 2766 1106 2862 2093 22…
Output: 3164

Example 3:

Input: 2 0
Output: 1

Constraints:

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

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