CT44134

Mina's Woven bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the port of Emberfall, Mina records each bridges in a worn leather ledger. The guild wants answers, not guesses. 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 <= 1633; 0 <= m <= 3266; 1 <= u,v <= n.

Example 1:

Input: 544 783 21 283 34 279 442 462 171 271 18 465 123 270 239 461 23 68 216 223 62 401 351 352 194 490 434 543 180 477 237 337 357 519 169 224 49 436 316 426 182 530 233 307 435 490 56 432 481 535 364 430 141 445 141 192 17 266 175 517 237 250 43 513 137 427 214 297 268 418 64 507 278 342 230 314 26 303 366 456 33 175 101 112 54 85 50 179 134 309 72 336 121 369 78 473 312 436 111 199 255 357 184 396 160 366 64 402 26 115 90 248 282 349 323 427 296 431 293 384 404 473 104 508 156 452 178 477 94 260 201 229 434 534 85 406 333 398 3 141 28 530 64 451 196 463 74 265 264 544 42 196 141 427 495 504 1 97 347 475 57 271 41 312 266 435 165 230 150 189 176 296 134 318 380 487 166 317 256 447 84 443 15 214 337 538 67 534 34 191 42 247 14 516 316 436 40 426 52 187 93 121 310 377 270 333 153 397 26 27 494 5…
Output: 35

Example 2:

Input: 544 162 495 516 90 420 71 535 237 478 172 397 233 498 239 259 284 295 301 443 300 372 1 399 29 498 67 494 165 489 285 365 50 148 63 150 134 345 253 408 385 521 203 272 109 341 145 381 10 263 273 525 52 111 203 294 157 472 136 163 247 311 145 318 143 183 191 528 218 226 367 437 69 409 16 300 156 360 116 398 449 527 280 513 47 74 82 325 300 509 12 177 290 530 185 505 397 456 179 363 106 534 434 500 40 83 192 441 140 144 167 237 138 203 129 265 88 425 6 157 374 540 22 85 52 159 380 429 92 177 182 527 175 330 88 503 134 270 47 245 364 411 229 506 114 509 185 432 281 328 236 259 77 258 154 345 309 315 289 420 310 450 9 307 425 483 18 216 125 247 122 371 128 412 490 491 236 408 145 310 327 388 33 34 40 424 214 337 81 371 244 358 52 387 2 88 125 390 236 396 171 264 105 352 223 441 327 536 4 350 2…
Output: 382

Example 3:

Input: 544 2201 86 104 166 348 83 249 93 124 153 446 151 419 27 114 362 501 252 371 89 115 28 316 27 350 193 224 136 242 292 304 234 290 230 537 72 85 259 351 251 392 84 91 123 229 10 131 203 543 115 185 306 479 25 324 27 89 73 238 332 447 70 134 191 352 124 276 424 537 327 342 165 273 134 355 52 67 114 516 17 138 56 436 188 222 179 466 331 419 70 85 7 274 29 87 108 476 39 43 292 427 254 475 7 257 49 504 180 189 314 514 82 380 90 254 287 510 309 478 93 120 310 392 213 227 89 223 12 16 113 148 11 270 375 489 105 441 83 380 195 307 101 262 368 420 40 438 73 447 254 503 75 132 21 521 179 484 21 344 371 527 64 445 23 456 411 430 296 390 497 502 35 186 228 277 359 427 66 370 145 178 106 107 103 119 99 294 521 539 196 244 196 489 96 461 200 293 48 321 291 416 298 484 42 428 106 215 402 446 65 193 195 2…
Output: 1

Constraints:

1 <= n <= 1633; 0 <= m <= 3266; 1 <= u,v <= n.

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