CT48198

Kael's Ledger of roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Kael the scribe watches over the pine barrens of Needlepoint's stores of roads. A careful computation stands between order and chaos. 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 <= 2712; 0 <= m <= 5424; 1 <= u,v <= n.

Example 1:

Input: 1126 1082 165 1126 403 990 53 748 521 906 87 816 346 355 98 305 216 422 4 224 654 1007 22 738 721 1015 278 322 68 296 369 880 150 823 280 509 361 1092 287 921 323 980 183 575 320 878 214 514 532 728 35 731 326 519 388 659 298 1071 225 1109 910 1072 391 519 768 951 739 774 398 997 125 893 210 1081 373 563 268 386 43 943 779 979 664 861 745 921 975 1117 402 857 192 874 787 862 314 317 470 677 175 1041 305 348 454 693 33 1087 42 443 938 1062 798 1052 187 956 578 797 93 1023 876 1006 936 1115 106 1082 177 604 637 901 584 682 863 996 292 715 234 646 600 1079 384 696 573 1042 11 693 437 1050 241 511 64 1121 259 414 708 995 562 927 368 487 82 908 378 388 361 768 735 1022 786 1117 208 757 111 472 1 848 145 195 310 982 124 242 161 442 862 921 94 1071 207 891 553 1006 75 887 78 136 578 826 392 724 1…
Output: 196

Example 2:

Input: 1806 681 245 831 227 1623 854 1190 1269 1324 310 1266 237 273 305 1089 697 803 561 1734 392 1510 1495 1611 522 1509 1251 1670 339 1133 241 334 171 1235 413 1714 224 732 444 984 447 1332 803 1295 1583 1651 110 1224 53 913 508 1789 663 1633 560 1661 1132 1604 208 511 350 1261 264 266 498 740 824 1248 614 1062 878 1559 1726 1740 980 1642 12 303 597 902 623 682 186 1500 152 1423 406 991 1283 1476 489 1468 417 1573 858 1282 661 1475 310 335 181 630 61 300 605 1241 1098 1784 782 1563 869 1773 138 882 592 1030 151 386 146 1744 931 1160 171 1001 1194 1217 1200 1480 573 1181 1122 1290 955 1075 123 1394 742 1168 770 1764 417 902 82 840 420 704 196 245 1051 1069 1761 1801 183 386 767 916 109 550 1357 1677 355 901 107 1759 1045 1564 10 1768 758 1445 344 416 1073 1712 379 1151 213 1145 766 1371 1168 14…
Output: 1125

Example 3:

Input: 2004 543 929 1553 1690 2002 1557 1687 50 1972 1169 1375 787 1214 323 1263 436 1808 947 1677 567 1116 1140 1650 792 1523 524 1985 222 1801 836 1089 732 738 1599 1659 263 1264 361 854 365 978 583 994 125 1835 317 854 660 1297 810 886 192 1648 99 373 281 1724 100 1002 110 288 82 537 948 1273 505 518 374 1809 762 1073 418 505 392 1988 698 834 1034 1409 1237 1408 1984 1993 1517 1585 675 1137 1024 1224 761 1378 200 649 1026 1680 730 1654 973 1050 16 957 507 1622 1156 1971 547 1519 200 601 326 447 287 675 864 1931 1073 1871 363 1137 32 253 445 861 337 802 230 870 146 1132 211 345 177 962 1217 1797 190 340 83 508 1889 1894 613 1111 102 748 140 561 1232 1325 1111 1137 678 923 673 1123 1423 1798 30 822 135 975 83 522 933 1421 956 1296 1625 1978 282 1246 1048 1428 1188 1638 96 453 1261 1559 75 1518 4…
Output: 1461

Constraints:

1 <= n <= 2712; 0 <= m <= 5424; 1 <= u,v <= n.

Loading...
Test Cases:No test cases
No test cases available.
Kael's Ledger of roads - MEDIUM Coding Problem | CodeTikki