CT41719

The Granite Separate Camps

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Axel inherited the shed at the northern keep of Frostgate along with its curious bookkeeping system for routes. Time to make sense of it. Task: An undirected graph has n nodes and m edges. Print the number of connected components. Input format: First line: n and m. Next m lines: u v. Output format: Print the component count. Constraints: 1 <= n <= 1740; 0 <= m <= 3480; 1 <= u,v <= n.

Example 1:

Input: 245 1963 179 237 70 139 62 67 176 230 108 115 84 178 62 112 126 142 44 68 85 150 88 178 23 175 37 54 57 244 109 226 43 134 3 193 56 112 75 226 124 217 81 194 55 139 11 232 66 110 52 182 133 199 87 177 36 215 17 66 9 158 82 206 165 230 40 227 183 211 51 90 42 76 201 221 136 206 115 178 78 90 180 230 158 167 24 56 121 194 61 125 106 142 136 232 226 237 30 108 157 196 210 236 7 179 194 206 101 155 106 214 174 206 155 157 5 29 6 32 67 231 22 220 179 214 122 181 11 37 34 51 12 17 65 156 136 165 102 168 46 74 32 195 68 125 123 146 27 123 91 235 100 165 98 131 102 218 58 173 171 236 86 212 66 71 49 201 104 158 94 204 99 165 35 47 137 237 29 94 83 126 188 213 25 78 79 226 143 231 161 173 41 186 168 210 30 76 130 143 98 150 147 184 58 86 2 55 34 103 81 155 11 66 1 181 85 127 145 163 15 49 84 180 14…
Output: 1

Example 2:

Input: 1634 1043 1056 1111 493 630 1225 1608 261 1068 363 1141 70 699 549 1047 105 866 153 1148 463 712 874 1521 708 1264 38 287 363 532 58 97 213 325 372 1362 557 656 468 497 1124 1605 357 646 255 596 97 423 1474 1632 1055 1180 752 1231 853 1373 67 757 141 913 1028 1459 257 997 113 1228 255 1455 482 636 661 1224 949 1071 122 245 264 1521 315 1517 201 272 353 601 1003 1284 92 838 197 1446 371 879 151 1535 286 698 68 532 311 1225 648 1004 115 468 832 1449 989 1503 455 1378 149 1486 1319 1490 1153 1400 435 673 282 1033 225 687 505 1257 219 281 197 452 119 525 734 1295 726 1076 218 922 262 805 211 1345 159 224 654 1400 111 826 127 1517 689 859 29 1123 121 1207 868 1093 210 948 833 942 1441 1616 436 1607 246 733 881 1595 1013 1344 739 1532 102 288 922 1588 561 1598 1020 1097 76 987 1354 1628 99 172 2…
Output: 597

Example 3:

Input: 242 117 95 153 31 151 76 205 85 238 70 99 69 146 3 23 71 115 172 218 47 58 172 185 75 109 45 49 142 219 79 157 8 197 45 241 179 183 113 168 149 212 74 82 71 161 198 202 129 140 124 191 137 179 36 115 41 49 48 219 191 192 94 106 167 226 110 143 147 217 26 63 148 190 2 93 26 92 8 115 17 221 10 114 66 164 125 197 202 226 22 46 50 64 3 136 57 68 65 206 1 66 90 196 62 112 135 224 18 208 93 215 208 216 22 228 4 35 90 152 127 209 51 224 14 73 120 206 82 227 13 28 93 111 12 136 90 181 4 195 84 139 24 131 150 211 70 96 165 211 71 123 8 94 131 175 79 88 19 233 126 227 113 238 61 95 12 172 84 225 31 144 214 223 115 223 113 139 99 215 8 99 21 90 8 123 74 188 166 186 160 224 85 172 131 220 103 105 78 159 108 236 52 224 115 141 29 96 126 232 129 184 148 192 105 240 139 142 88 231 106 184 89 100 38 133 5…
Output: 126

Constraints:

1 <= n <= 1740; 0 <= m <= 3480; 1 <= u,v <= n.

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