CT51655

The roads Separate Camps Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the island market of Coralcove, someone must rank apprentices for the new term. This year the task falls to Theo, armed only with the roads register. 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 <= 3817; 0 <= m <= 7634; 1 <= u,v <= n.

Example 1:

Input: 2299 3532 973 1660 106 991 1263 1582 1084 1222 83 728 203 349 1505 1974 867 1037 404 1527 156 733 1230 1241 612 2106 59 1241 1239 1445 367 1440 454 1301 136 820 947 1020 940 1376 35 2182 420 915 474 1912 299 564 224 1792 186 1172 755 992 1132 1453 2005 2012 1785 1922 41 497 533 918 666 1526 1283 1460 928 2226 251 706 361 852 974 2059 1217 1396 1395 2023 463 1788 1155 2112 948 2197 330 1824 1238 1963 475 1774 1456 2089 368 678 715 882 536 1879 888 1304 1631 2011 253 1725 1471 2255 1162 2044 1212 1387 387 1024 747 881 755 1492 558 1132 1042 1475 1340 1962 197 2207 1581 2004 83 1235 750 2088 45 1613 510 1035 812 1216 314 1099 140 1849 950 1045 1254 2178 426 804 120 262 1345 2294 766 897 106 1391 891 1934 633 2239 1338 1543 518 1740 584 1116 2188 2266 224 1488 1170 2256 505 2189 1132 1275 1463…
Output: 102

Example 2:

Input: 3601 4978 438 2571 21 1124 1735 2621 1114 1396 3365 3417 1534 3256 709 1811 2224 2664 1144 3254 2798 2829 2390 2743 512 2365 1064 1707 938 3190 2341 3111 2522 3440 1831 3308 911 2800 2910 3067 734 1464 557 2191 1991 2536 672 817 29 2136 1302 2127 2663 3371 717 2639 670 2037 1367 2676 1988 3305 187 1176 2049 3086 359 2809 519 2961 1101 1893 612 1730 327 1145 109 779 657 2096 252 3184 163 2410 1309 1939 1138 2136 1708 1913 9 2479 1461 2414 1063 1445 1564 2940 827 1744 800 2495 2551 2971 495 596 837 3057 2521 2919 3121 3394 240 1221 812 2948 679 792 920 2156 1560 2647 316 2342 1040 1438 571 3579 127 511 2408 3285 915 1700 829 3298 2474 3117 203 1925 2108 2137 241 3226 171 1573 1510 3522 1049 1317 1458 3310 2954 2976 855 1069 2066 3562 607 1151 1217 1700 1719 3339 2079 2498 1675 3476 853 3092 …
Output: 247

Example 3:

Input: 1891 5316 836 1804 1198 1613 1146 1590 134 536 33 290 174 279 269 1311 1190 1374 248 1626 79 204 353 1107 648 1424 1577 1613 491 1182 147 202 684 868 653 1503 243 1849 17 545 11 463 1188 1194 928 1742 375 443 1493 1870 231 637 319 806 98 538 426 1176 539 1686 822 1858 1265 1464 400 1053 1437 1625 55 510 156 690 855 1186 11 378 67 228 684 1091 669 905 733 892 57 1876 110 1367 944 1280 1049 1555 552 606 1429 1539 287 1383 345 1751 166 322 702 1222 108 957 963 1580 220 1767 548 1421 1384 1555 1088 1582 325 819 370 1696 437 476 911 1614 425 1792 528 1608 1139 1739 1007 1309 777 1123 260 619 1709 1764 1674 1727 182 1109 399 672 465 1464 1599 1815 1390 1466 651 926 464 836 100 1649 546 1594 288 369 607 827 1095 1301 288 1870 142 594 274 1831 1118 1207 1424 1852 788 1335 1319 1738 324 1475 826 16…
Output: 8

Constraints:

1 <= n <= 3817; 0 <= m <= 7634; 1 <= u,v <= n.

Loading...
Test Cases:No test cases
No test cases available.
The roads Separate Camps Puzzle - MEDIUM Coding Problem | CodeTikki