CT45178

The Separate Camps of Cinderline

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the railway depot of Cinderline close for winter, Kate must finish the bridges ledger - one figure at a time. 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 <= 3505; 0 <= m <= 7010; 1 <= u,v <= n.

Example 1:

Input: 1781 4000 329 660 367 1682 413 849 299 1654 379 724 188 443 372 1291 263 1377 189 484 614 1461 320 1607 419 1071 474 1317 60 446 792 1466 124 1093 961 1142 1632 1712 54 931 591 1549 629 1436 1504 1653 460 1080 1319 1499 670 1455 939 1543 373 1758 920 1747 1307 1669 190 1277 490 781 459 1470 851 1546 147 1723 779 959 755 925 66 826 415 1685 450 1422 1085 1669 132 1142 380 617 1075 1728 1195 1685 721 1746 417 1658 570 1756 659 1731 191 915 490 1361 1054 1770 303 977 469 942 845 901 1314 1493 565 1752 250 1336 713 1679 299 450 875 1364 992 1626 222 299 132 476 116 210 158 774 280 664 826 1033 591 847 15 1521 542 1322 1001 1745 132 197 1448 1632 324 1612 1249 1717 1017 1314 207 1242 220 948 335 711 360 927 1252 1624 1422 1454 191 611 553 1576 530 1005 179 601 321 1568 10 363 360 373 1284 1409 …
Output: 22

Example 2:

Input: 2366 3460 69 1046 2051 2167 554 683 1677 2276 1864 1959 416 708 786 1138 751 1408 1687 1955 335 672 1063 2085 1549 2263 399 996 1454 1875 1519 2269 163 851 739 1636 205 2359 1029 1225 1706 2351 20 668 1261 2090 1320 2135 261 1089 531 1085 1969 2327 1400 1947 1151 2198 297 1208 1277 1597 260 1368 605 1695 552 1439 1486 2290 241 1089 1838 2235 1370 1527 1679 2113 176 981 428 1602 1137 1917 299 1767 322 572 1771 2222 75 411 44 2356 1304 2121 665 1165 177 1382 298 1182 588 2050 57 1758 1376 2336 595 723 388 766 1884 2172 31 2345 562 2025 21 865 767 2137 105 1213 2091 2358 924 1363 9 601 1625 2350 1493 1792 81 2086 882 2107 535 1697 108 2073 1518 2010 179 1944 636 1396 152 1088 512 625 953 1546 1330 1997 1899 2085 2026 2125 90 1681 1037 2356 350 1207 1456 2364 933 1041 667 1530 536 792 2202 233…
Output: 146

Example 3:

Input: 1173 3576 122 696 331 879 732 821 519 853 1047 1073 519 962 112 178 804 1001 1001 1142 254 1012 353 705 584 991 43 486 598 761 636 1062 71 377 388 877 432 706 641 1027 737 821 14 36 881 1153 991 1116 254 543 404 616 372 661 170 724 625 650 77 1024 163 910 332 1047 102 781 240 909 208 264 433 953 329 848 313 869 571 1138 141 1075 490 858 765 1038 196 405 42 1133 549 601 458 676 820 1025 383 944 335 1128 716 1146 744 1079 833 963 1103 1170 396 843 1005 1102 463 736 293 389 121 670 441 694 912 939 680 689 463 1059 95 826 652 1000 470 822 22 1124 452 1167 327 923 838 1052 792 949 348 867 289 957 226 298 844 858 3 25 376 628 393 998 170 985 683 718 586 1148 1017 1165 838 932 215 735 532 1099 259 495 406 927 788 925 21 939 692 1010 172 972 189 439 570 800 77 1055 192 842 818 1135 179 782 269 424…
Output: 2

Constraints:

1 <= n <= 3505; 0 <= m <= 7010; 1 <= u,v <= n.

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