CT52573

Keeper's Obsidian bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the rookery of Crowhaven as Keeper unrolls the day's manifest of bridges. 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 <= 1935; 0 <= m <= 3870; 1 <= u,v <= n.

Example 1:

Input: 913 3218 588 817 335 533 24 524 603 652 286 706 204 472 546 615 93 761 318 541 191 263 488 585 740 807 2 565 9 820 77 439 50 578 559 624 172 514 246 394 167 278 423 580 319 820 337 762 156 212 647 676 80 727 124 330 97 204 76 425 138 365 602 779 575 912 92 391 63 781 697 829 318 845 440 721 57 220 239 795 147 247 118 229 65 717 424 618 28 81 165 766 363 905 343 602 590 840 114 387 692 808 348 695 102 144 165 524 447 531 336 813 138 214 57 656 487 589 511 656 63 116 194 828 26 504 65 688 121 731 541 876 464 793 214 745 331 732 695 796 467 849 266 583 672 850 157 705 75 606 97 792 131 334 487 645 83 99 552 645 46 159 257 442 720 843 50 96 231 670 340 357 283 477 543 877 234 785 20 292 385 844 35 898 617 753 455 843 52 521 271 419 132 243 551 837 77 905 408 501 510 592 637 676 34 653 209 264 …
Output: 2

Example 2:

Input: 1926 3430 265 445 595 839 235 1538 420 1414 1295 1580 555 1655 1323 1756 523 1723 350 1152 27 313 52 1298 468 969 1081 1176 236 553 390 975 879 1526 407 898 995 1429 785 1178 946 1129 503 1320 327 618 630 1151 196 1809 1158 1880 480 1073 229 1000 663 1495 559 1847 826 1465 992 1848 103 354 1740 1849 49 1567 967 1153 622 1735 1588 1808 1904 1908 147 1051 225 1772 116 1020 1231 1833 147 1551 1023 1694 43 908 602 1815 755 1699 405 1267 299 681 888 1550 354 1825 1051 1214 50 945 80 844 333 883 156 1303 698 1415 1341 1806 738 1248 805 1816 1161 1793 1092 1544 1170 1641 1135 1429 424 937 374 1313 1788 1883 774 946 1045 1252 867 1398 76 545 1343 1376 625 1078 271 1633 1157 1519 771 962 114 959 267 1835 210 1098 858 1592 1342 1542 504 1750 1446 1584 1324 1436 176 493 78 769 65 566 189 236 1454 189…
Output: 73

Example 3:

Input: 1123 2038 207 385 269 647 94 648 937 1055 762 828 595 713 43 508 129 1037 389 911 129 368 54 750 375 959 617 734 120 965 253 1006 473 1022 603 868 581 907 255 998 683 772 590 1119 133 659 835 857 896 974 671 732 405 523 153 620 667 928 59 404 774 828 126 1104 31 35 184 697 872 1047 159 227 857 1108 367 720 77 368 419 930 188 304 204 1091 598 716 493 865 105 934 462 744 316 540 651 727 174 575 176 616 298 1005 384 512 1018 1072 451 455 438 586 208 648 169 1120 292 873 249 380 849 966 153 494 305 540 206 991 43 496 626 755 624 1070 701 988 880 906 360 547 437 782 522 655 147 644 222 447 562 822 305 638 49 302 373 992 539 661 163 463 615 797 765 803 775 1093 329 555 17 817 827 976 276 527 514 711 878 947 657 689 649 982 136 575 462 621 632 1096 104 1000 289 313 70 431 462 586 785 1089 637 819…
Output: 32

Constraints:

1 <= n <= 1935; 0 <= m <= 3870; 1 <= u,v <= n.

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