CT32592

Draper's canals Reckoning

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Before the gates of the mining town of Ironvein close for winter, Draper must finish the canals ledger - one figure at a time. 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 <= 1066; 0 <= m <= 2132; 1 <= u,v <= n.

Example 1:

Input: 942 1361 139 840 617 626 341 380 28 499 271 708 582 779 420 460 462 551 373 587 132 627 618 823 393 483 2 383 377 828 6 309 413 941 294 876 299 620 19 360 538 626 66 228 186 677 220 714 406 616 87 644 441 806 138 267 68 686 858 907 32 532 639 720 516 911 43 189 533 544 496 572 565 878 100 166 234 334 278 588 489 831 142 435 355 926 258 902 794 806 363 853 385 910 15 77 213 365 390 497 221 805 182 355 659 876 421 693 620 926 443 752 207 244 561 821 1 483 576 592 224 562 3 760 98 359 107 739 544 689 23 521 295 576 313 334 701 840 257 405 82 347 377 908 18 214 377 508 731 806 279 568 309 472 572 787 321 768 289 361 79 386 223 501 87 250 720 938 202 500 114 284 104 488 663 887 259 518 217 618 333 639 716 913 380 768 111 505 169 776 271 742 3 107 165 446 239 871 195 925 150 316 285 868 206 483 …
Output: 59

Example 2:

Input: 401 130 227 342 171 392 23 91 34 167 93 145 139 187 143 376 96 351 259 352 36 260 177 314 94 367 328 379 47 230 233 378 18 390 59 371 49 207 190 287 277 342 210 390 67 198 224 348 213 253 269 389 28 384 91 165 142 235 129 178 10 58 207 297 119 345 189 257 99 180 297 327 186 345 27 273 160 244 185 247 124 167 18 48 137 201 101 157 82 376 72 201 36 47 50 73 219 279 43 245 196 310 90 107 18 189 164 269 123 178 271 311 77 157 352 373 72 253 135 395 134 378 304 376 86 221 150 358 25 291 16 125 69 299 62 317 87 212 141 279 77 292 54 279 64 123 16 257 246 290 279 354 301 336 131 299 189 295 113 170 112 147 144 261 82 124 262 362 335 366 261 336 180 188 242 323 117 291 34 113 172 195 210 262 93 204 139 263 208 306 115 223 81 258 130 271 283 391 105 296 15 267 64 285 325 379 129 298 246 385 353 355…
Output: 271

Example 3:

Input: 283 830 35 57 7 144 159 213 189 252 91 283 168 231 26 266 43 231 108 263 97 250 58 89 130 134 8 247 36 94 192 258 59 147 252 253 40 272 29 258 150 153 138 189 241 244 145 270 33 51 24 266 126 198 71 276 55 115 20 108 94 152 39 149 9 95 194 224 44 144 128 275 77 135 76 282 108 201 151 212 121 200 106 220 48 109 20 272 93 190 147 160 156 158 257 259 120 135 166 267 92 277 33 123 8 215 51 235 50 59 23 209 1 231 139 246 276 282 44 136 18 226 95 257 60 123 44 217 159 179 26 221 237 256 96 170 98 198 18 221 122 160 193 282 45 61 123 141 120 193 239 260 82 276 142 264 145 181 22 98 168 253 99 136 100 229 92 142 182 223 128 143 169 178 175 223 235 278 141 272 245 272 105 253 223 248 168 251 93 126 215 247 105 210 91 157 202 282 26 226 72 85 158 280 103 224 29 183 140 273 135 161 55 94 15 212 184 2…
Output: 2

Constraints:

1 <= n <= 1066; 0 <= m <= 2132; 1 <= u,v <= n.

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