CT46843

Yusuf's Hidden roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the orchard lands of Applerun, someone must plan the harvest festival. This year the task falls to Yusuf, 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 <= 3013; 0 <= m <= 6026; 1 <= u,v <= n.

Example 1:

Input: 1952 3954 748 1176 98 1055 741 760 281 1842 1066 1322 1165 1692 695 1416 673 1191 1256 1259 219 351 1313 1433 1238 1406 73 1682 175 1622 89 1566 147 1171 766 1576 679 1364 1053 1722 1030 1196 681 1091 926 1308 446 1185 399 1489 725 1904 1284 1741 777 1101 879 1755 104 1284 1539 1620 205 1923 510 1900 377 1189 1089 1114 1544 1737 775 898 491 607 279 469 1610 1878 1521 1793 1209 1872 903 1110 175 1074 168 1437 118 372 298 637 1474 1826 111 1900 1167 1175 1270 1614 1206 1321 511 924 280 1706 1531 1837 1300 1709 1382 1902 594 869 501 1400 27 1656 460 1313 245 403 513 1487 313 1254 176 435 585 1147 352 1235 691 1515 525 1316 1406 1504 595 1302 454 667 15 1169 194 1759 907 1015 1344 1451 444 1093 1130 1556 257 450 596 1017 659 1154 639 1197 671 1906 838 890 769 961 1144 1373 905 1678 877 1884 77…
Output: 36

Example 2:

Input: 1592 550 18 551 303 570 156 1298 1079 1371 784 1326 1170 1177 42 1197 997 1422 11 1577 386 690 116 757 171 1430 428 1355 656 684 16 1259 671 1287 331 1127 467 663 99 1285 572 1495 530 1137 650 982 110 1277 430 1224 143 699 195 494 1403 1592 82 996 59 748 179 988 344 852 76 1390 836 1114 127 1358 214 965 101 1097 1363 1510 230 663 1203 1542 392 718 728 1300 1100 1254 312 1000 1357 1531 1171 1518 533 1011 31 489 3 515 528 1577 812 1431 1369 1521 180 1031 39 88 1 61 200 931 1182 1367 704 1279 513 1520 183 1448 361 791 1372 1491 639 1071 1085 1302 945 1207 472 1185 521 1094 594 1517 163 1511 12 491 222 1405 1199 1434 228 734 434 1449 458 647 336 968 411 1515 504 1274 1151 1321 594 758 52 1113 306 1437 686 1231 467 476 1182 1456 356 1070 389 1081 311 725 1229 1418 340 1126 1019 1518 295 440 83 …
Output: 1042

Example 3:

Input: 906 2645 408 731 138 706 32 256 474 710 79 875 68 231 436 577 368 481 333 491 159 359 72 796 161 540 316 815 172 251 261 296 518 798 568 858 31 180 155 597 61 101 622 876 143 715 15 295 679 766 381 729 373 588 182 461 83 466 41 649 23 409 450 742 736 765 600 843 127 519 623 764 329 372 312 574 124 622 297 854 246 725 136 209 551 577 527 596 423 878 232 828 295 494 56 298 162 814 238 398 88 669 219 833 645 791 42 332 281 734 354 884 15 290 148 561 689 783 1 625 849 879 33 259 287 767 612 753 37 318 23 730 64 483 340 399 260 674 128 582 46 772 25 236 671 850 128 636 488 760 577 642 233 770 191 203 542 611 171 896 623 889 469 643 812 834 629 782 522 532 535 848 106 345 263 884 82 378 390 550 33 362 59 230 530 637 63 563 128 407 63 331 555 864 350 691 723 839 304 780 105 896 174 455 25 660 356…
Output: 4

Constraints:

1 <= n <= 3013; 0 <= m <= 6026; 1 <= u,v <= n.

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