CT30649

Sahil and the Jade corridors

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Legend says the vault under the monsoon port of Rainhaven opens only for a perfect tally of corridors. Sahil means to find out. 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 <= 729; 0 <= m <= 1458; 1 <= u,v <= n.

Example 1:

Input: 688 96 88 138 138 354 624 685 562 670 43 275 413 495 77 602 205 662 433 460 121 134 58 303 453 662 172 670 387 418 303 458 79 449 308 677 547 629 88 537 22 157 99 629 22 251 298 563 524 545 209 319 423 440 127 164 391 429 172 538 191 465 349 540 163 400 57 652 450 632 118 193 332 679 8 236 167 555 40 387 28 327 447 573 151 556 334 536 116 582 267 355 100 516 40 538 34 40 35 465 106 401 116 574 115 421 648 665 567 654 58 579 51 656 133 442 79 507 479 646 185 457 73 214 279 664 76 575 251 580 159 181 50 299 355 682 159 258 404 570 31 152 113 506 48 476 15 624 336 602 223 298 40 376 66 431 165 268 87 581 393 576 239 404 117 300 72 519 417 481 87 489 152 194 361 492 175 650 109 662 526 609 35 371 462 509 6 422 405 671 78 403 525 633
Output: 592

Example 2:

Input: 552 1354 325 526 171 320 335 458 101 439 316 383 110 190 64 271 85 469 324 396 314 480 341 422 21 435 217 322 128 371 96 150 290 406 502 503 127 320 105 203 481 493 250 463 145 500 363 468 372 552 20 155 348 409 153 170 157 288 300 360 36 241 232 525 266 402 141 360 423 512 430 512 105 448 32 470 112 480 305 375 96 384 114 189 236 459 471 501 3 258 397 483 4 37 86 213 222 388 138 526 226 311 360 483 142 395 33 37 331 477 87 110 283 419 27 50 22 38 67 354 386 445 353 450 254 255 33 302 299 504 87 267 59 204 48 79 463 487 70 271 291 368 92 223 332 511 198 223 148 365 32 63 125 277 249 366 92 173 150 312 2 332 93 523 82 134 459 519 284 454 153 412 17 447 238 525 353 372 108 245 326 362 229 546 243 317 262 275 85 218 174 448 221 395 200 407 470 504 130 317 44 415 421 510 90 114 222 488 72 288 …
Output: 2

Example 3:

Input: 117 207 37 68 11 55 63 114 3 83 53 67 14 15 1 37 51 111 70 95 23 81 45 65 96 99 10 108 54 62 49 78 64 94 65 84 28 89 100 109 30 66 17 81 67 93 78 117 2 107 39 40 71 110 9 72 48 95 81 93 63 78 16 42 31 52 83 99 42 110 54 72 46 78 18 71 69 83 24 71 4 44 1 89 2 98 22 108 28 76 38 47 42 84 31 33 7 66 78 88 70 80 52 108 78 86 9 35 59 106 22 97 19 40 27 74 13 17 53 60 71 116 80 116 56 86 7 34 25 76 14 99 7 116 94 105 36 63 60 65 101 105 46 76 58 72 9 92 68 114 11 86 42 74 10 18 36 70 58 111 56 75 18 76 103 117 37 70 65 75 5 91 65 66 38 94 4 59 9 47 12 110 92 107 47 80 6 40 88 90 12 111 22 35 69 73 63 85 10 73 11 117 57 98 16 74 55 101 32 48 46 98 27 117 73 91 57 70 42 49 62 105 44 74 20 41 12 108 1 14 63 75 5 117 58 82 8 29 13 100 66 71 12 79 19 75 71 85 40 96 36 98 21 103 7 9 51 109 34 92 25 69…
Output: 2

Constraints:

1 <= n <= 729; 0 <= m <= 1458; 1 <= u,v <= n.

Loading...
Test Cases:No test cases
No test cases available.
Sahil and the Jade corridors - MEDIUM Coding Problem | CodeTikki