CT33525

Dora's corridors Reckoning

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Morning light hits the basalt cliffs of Obsidian Shore as Dora unrolls the day's manifest of corridors. The tally will decide the next shipment. 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 <= 1664; 0 <= m <= 3328; 1 <= u,v <= n.

Example 1:

Input: 988 1995 171 612 227 431 131 438 858 952 36 979 857 979 164 527 131 375 413 780 80 175 333 880 710 888 200 209 465 845 742 835 22 970 189 851 61 142 376 826 284 438 596 914 197 379 143 272 7 938 669 762 178 788 16 832 39 315 542 727 61 804 243 271 175 568 519 725 144 386 555 776 360 768 703 868 599 878 579 759 547 969 347 374 536 673 173 434 548 725 315 820 350 527 36 746 50 915 168 274 309 748 471 643 368 651 651 728 55 437 210 940 357 405 116 838 263 668 209 942 406 428 18 881 754 977 266 663 96 822 564 636 130 900 50 947 224 232 240 462 556 788 172 458 43 660 166 794 204 691 128 800 70 670 512 588 564 765 1 95 298 403 31 183 611 761 483 950 75 201 789 982 131 642 863 878 466 871 36 768 234 984 22 616 294 770 148 765 423 586 391 412 449 768 162 764 682 771 540 831 126 966 215 349 219 408…
Output: 14

Example 2:

Input: 1275 2777 43 532 465 1195 65 1051 48 1249 430 1138 276 944 210 489 90 249 667 845 257 601 5 523 190 632 180 697 341 1063 351 1219 191 679 589 1061 185 806 321 1093 180 596 438 1007 40 706 49 1270 500 620 1100 1136 36 479 975 1117 723 1251 340 555 58 377 526 677 91 1271 244 801 313 999 1134 1273 551 882 258 845 20 1159 199 207 487 1072 708 782 672 724 46 1026 561 787 623 864 384 799 155 565 165 1000 1136 1204 1262 1273 42 161 566 1195 352 591 172 736 565 828 80 1223 3 94 337 1083 184 264 1207 1247 230 448 35 275 597 707 927 1250 50 913 425 883 542 884 99 467 11 936 51 846 326 654 453 1242 347 393 431 1100 93 861 26 667 1074 1213 97 776 284 580 94 413 694 874 144 263 1036 1249 294 1081 436 566 393 1082 253 846 26 1110 771 1248 234 1118 532 567 40 254 29 582 42 621 835 878 304 1273 115 1041 5…
Output: 21

Example 3:

Input: 771 1746 316 695 568 699 449 708 332 333 362 464 301 546 464 603 425 709 175 452 14 410 295 759 145 653 311 371 7 360 453 663 274 313 55 455 142 180 326 471 153 718 312 454 204 715 341 442 267 412 509 535 275 464 86 342 105 564 319 509 5 120 65 276 274 682 310 763 183 353 82 697 184 481 429 663 36 662 49 468 166 593 270 354 180 569 602 709 72 408 649 748 419 673 159 606 506 720 44 174 356 595 344 373 274 559 438 486 52 125 2 579 252 582 476 527 592 703 43 636 82 298 163 475 156 533 162 732 596 643 76 430 142 748 45 149 326 643 420 723 53 648 178 475 189 449 447 531 722 739 304 618 110 471 11 721 313 751 86 122 126 340 13 756 81 319 57 579 205 309 572 579 572 686 8 368 266 282 254 762 36 79 64 96 375 425 37 371 35 225 130 172 292 771 35 691 180 182 90 757 165 482 225 510 720 767 25 359 577 …
Output: 7

Constraints:

1 <= n <= 1664; 0 <= m <= 3328; 1 <= u,v <= n.

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