CT36991

Cressida's Granite Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the terraced vines of Grapehollow with crates of signals, and Cressida the log keeper must account for every last one. 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 1714 4556 8881 9431 9747 8415 9265 4442 9506 5755 9676 2442 3016 3906 7483 2156 2189 5726 8481 3532 9537 1393 7729 6985 9117 1944 2790 5093 7483 807 5541 2607 8095 8022 8709 1952 7049 2059 4400 2469 5912 3149 6113 1953 7076 5010 5643 1446 8735 1643 7850 6812 9053 1412 7745 6509 8277 3197 8505 1708 6091 9086 9234 1368 6790 7138 9718 2616 5010 2314 7582 979 9657 3552 3605 2427 3457 1254 7617 1769 8199 2921 3684 5518 9977 959 7891 6473 9776 1148 7872 205 6908 61 3837 154 416 2301 6390 713 4220 3212 6416 3965 8890 4289 8155 1884 8105 1066 1304 2045 3692 1743 2745 1897 2624 2452 4407 5314 7741 714 5083 2968 3052 4864 7439 1984 8020 504 854 5682 7436 546 5556 4916 9418 7159 8893 1831 3926 4129 7085 2299 6871 1438 4839 5180 9313 2165 4207 2906 5772 2253 9961 981 9251 5098 6841 2101 6538 486…
Output: 8285

Example 2:

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

Example 3:

Input: 100 1857 31 94 38 41 65 98 19 96 19 24 38 58 57 59 17 99 63 65 20 31 19 57 7 14 30 95 62 87 28 93 16 21 4 80 8 56 19 29 9 22 23 38 20 62 32 33 93 96 41 45 70 75 52 71 67 84 71 83 77 96 18 52 7 15 28 83 44 47 29 80 41 46 20 51 12 20 64 83 96 97 62 77 23 94 29 89 28 70 3 35 79 80 31 57 21 38 31 89 7 26 62 72 40 73 56 66 50 74 59 88 42 59 44 63 4 14 56 83 23 93 72 86 79 92 59 68 29 32 23 86 21 91 20 71 14 98 17 42 45 69 78 93 75 88 29 72 4 24 37 59 31 53 30 66 40 92 11 43 60 82 21 86 34 93 22 28 41 89 13 41 18 45 19 63 77 92 3 19 85 97 9 43 17 47 7 46 3 25 77 86 39 100 13 47 68 85 17 78 12 63 18 88 11 49 3 45 42 65 53 62 59 62 15 30 13 21 37 79 16 48 18 78 13 70 3 20 76 80 73 95 31 95 24 32 84 92 35 54 40 55 24 46 18 19 31 99 26 65 47 72 2 30 65 93 35 63 68 97 3 17 18 32 33 83 24 59 75 79 15 …
Output: 0

Constraints:

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

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