CT36919

Ishaan's corridors Separate Camps

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ishaan found an old ledger of corridors in the ferry office attic at the alabaster quarry of Whitestone. 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 <= 2878; 0 <= m <= 5756; 1 <= u,v <= n.

Example 1:

Input: 1152 5494 803 1142 64 681 228 387 255 1041 271 858 655 949 235 1123 23 475 73 1070 68 1098 263 1126 6 798 524 591 438 805 392 818 231 995 500 603 327 547 357 1149 115 368 373 832 372 449 590 719 123 936 994 1092 567 592 392 417 738 1135 285 483 493 1104 105 378 465 1031 15 716 559 1045 267 324 10 684 172 729 505 584 603 1040 686 873 131 844 306 564 564 675 84 138 266 439 105 1120 60 346 101 486 55 1051 65 407 629 641 206 377 133 1040 375 773 230 554 159 1027 747 1151 593 894 395 1008 28 543 40 1035 491 1019 230 922 232 943 607 615 531 687 711 1074 293 956 349 369 198 714 580 670 170 739 86 945 261 778 113 1047 272 540 280 584 538 594 163 804 180 210 357 835 375 566 105 754 639 1145 336 937 212 274 287 1053 123 407 43 514 88 167 548 684 406 843 625 643 369 572 579 949 292 311 459 1073 36 63…
Output: 1

Example 2:

Input: 2623 539 174 2384 14 1266 229 887 315 1900 311 735 126 1663 2349 2604 1531 2349 553 801 681 2400 772 2459 1285 1545 1334 2610 355 1233 277 1884 370 1695 431 538 469 1103 330 625 368 1845 899 1979 427 2058 1193 1888 781 1351 833 2233 1496 2496 158 640 99 416 41 1224 581 881 296 1423 1660 2497 1771 1822 740 2058 525 1432 1313 2192 493 700 1945 1947 463 2191 508 1937 258 2518 426 1710 186 1611 1214 1422 64 1741 1310 2274 1165 2571 1718 1819 978 2597 322 1214 252 1287 2102 2259 301 1650 676 1357 995 1394 1103 2308 1268 1960 1094 1658 650 1917 1665 1832 1592 1883 200 667 868 1676 592 1766 1252 2279 1500 1599 766 777 1324 2038 454 2587 418 1377 694 2365 600 768 1352 1782 1376 1891 632 2077 485 1978 1865 2520 198 1330 1969 2257 160 1502 86 1415 692 1926 126 2548 253 1806 856 1815 80 1402 1308 235…
Output: 2084

Example 3:

Input: 2545 5143 1699 2225 504 1323 1454 1757 464 1494 503 1863 673 1459 11 195 295 2369 280 427 1632 2106 52 249 611 2397 1102 1918 942 2032 1009 2340 1152 1524 1069 1077 250 1861 684 2195 669 1354 842 1933 605 1761 418 2105 427 1586 1472 2473 139 2015 798 2446 1235 1645 359 1303 1929 2504 1191 1668 205 2483 380 863 754 1655 729 1222 822 2333 316 542 175 573 234 2506 202 2394 694 776 497 1155 1029 1404 471 585 968 1635 73 864 826 1625 832 1457 271 817 181 791 1300 1745 1223 1474 136 1272 452 965 1891 2077 962 1758 1506 2487 1592 2222 160 1145 969 978 382 474 654 2068 1285 2078 1712 2157 499 1549 352 1598 343 1255 1195 1348 1661 1886 1815 2019 1788 1966 257 1028 1205 1268 67 1920 498 2217 817 1687 868 1507 100 1114 372 431 589 1932 336 832 989 1040 85 269 234 1896 1031 2381 2043 2480 1149 2445 41…
Output: 55

Constraints:

1 <= n <= 2878; 0 <= m <= 5756; 1 <= u,v <= n.

Loading...
Test Cases:No test cases
No test cases available.
Ishaan's corridors Separate Camps - MEDIUM Coding Problem | CodeTikki