CT31979

Sage's bridges Reckoning

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Sage found an old ledger of bridges in the cooperage attic at the maple sugarbush of Saprun. The margin notes pose a precise question. 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 <= 1794; 0 <= m <= 3588; 1 <= u,v <= n.

Example 1:

Input: 1186 2882 773 1117 345 764 84 415 318 1143 447 1061 325 443 1009 1021 87 878 454 929 104 1051 588 939 140 612 751 1186 60 478 149 713 808 971 772 1110 300 599 21 957 394 419 113 921 321 1059 710 995 172 1006 612 1185 145 1080 363 731 71 256 895 1018 16 228 663 676 348 961 909 1136 363 570 230 454 914 1068 168 770 891 990 35 399 39 729 206 666 855 1023 717 830 691 886 564 989 61 378 298 1080 943 1141 733 1103 386 1145 806 1185 299 332 46 256 497 705 17 953 267 314 394 1107 781 1165 659 977 804 947 247 1005 211 679 506 833 2 1132 975 1017 394 1020 546 768 101 918 180 240 53 356 34 503 735 763 363 666 202 339 676 840 42 1012 162 798 65 565 331 1109 855 1006 86 1055 92 766 139 1067 746 793 112 538 518 996 38 1091 1025 1093 28 104 407 651 533 716 259 881 612 934 602 875 386 945 206 510 434 458 …
Output: 3

Example 2:

Input: 1241 938 455 888 84 948 130 341 236 824 198 291 616 1205 35 274 671 1219 481 941 152 804 237 869 411 475 402 1148 846 1006 11 293 200 965 13 1065 993 1125 405 1179 930 1225 676 792 737 823 344 481 592 1180 330 1153 284 1211 857 1119 82 479 158 266 164 918 53 450 390 1066 328 528 195 1226 1101 1236 656 685 545 987 56 138 715 929 72 82 230 852 635 778 58 118 737 968 217 453 171 694 252 856 177 535 453 937 10 1191 1169 1181 917 970 185 872 271 678 480 722 341 520 475 1145 226 678 150 1020 769 934 846 1061 365 782 569 1221 25 946 681 1183 147 1063 388 789 333 427 482 744 753 760 212 1066 425 688 742 889 659 1153 588 1140 526 985 556 713 718 1178 1067 1093 184 1139 279 717 1097 1156 258 481 167 1163 155 669 457 1138 301 983 418 462 166 225 371 614 361 955 202 878 693 1036 751 1070 336 856 935 1…
Output: 356

Example 3:

Input: 1606 1439 74 212 474 1262 63 862 121 347 497 1243 615 985 135 1186 42 341 816 1246 250 1575 679 1439 126 194 945 1401 1380 1544 756 1517 593 941 361 727 1045 1068 564 1036 70 1510 3 591 178 1418 449 961 617 663 145 205 81 1239 39 1337 583 902 889 1415 133 1384 88 862 217 234 113 154 698 768 468 631 206 703 629 1045 462 1492 1042 1108 238 276 657 1273 779 947 418 638 878 1592 242 978 730 996 605 788 1179 1276 444 945 830 1406 1368 1421 1170 1288 250 626 160 201 50 389 635 690 527 698 40 1298 867 1153 42 749 147 729 1184 1584 653 984 831 1150 261 1297 1205 1406 118 737 184 1571 474 1054 827 1569 69 932 570 765 845 1435 1273 1323 1384 1512 167 440 189 697 323 888 483 936 458 847 375 1113 1428 1596 649 856 330 533 1111 1282 119 270 456 977 225 1094 248 986 27 932 6 729 495 719 36 468 410 1462 …
Output: 306

Constraints:

1 <= n <= 1794; 0 <= m <= 3588; 1 <= u,v <= n.

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