CT39176

Curator's roads Separate Camps

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the ivory gates of Alabast. Curator spreads the roads records across the table and picks up a sharp pencil. 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 <= 2060; 0 <= m <= 4120; 1 <= u,v <= n.

Example 1:

Input: 1124 914 559 830 148 900 791 825 654 733 221 329 428 751 908 1059 44 572 532 670 113 811 7 750 33 608 132 1065 203 829 370 905 265 721 123 507 628 928 219 960 129 335 392 436 81 531 19 1114 104 447 304 588 134 991 132 827 770 1045 422 807 184 1041 520 902 610 1008 956 1052 23 1061 528 618 772 875 103 261 233 310 1043 1123 332 383 994 1057 929 1076 319 929 692 994 108 253 332 360 659 776 346 517 273 917 557 728 314 555 131 1030 918 1026 457 706 105 145 261 343 363 583 33 453 51 648 328 1117 928 1104 860 1089 122 585 565 1064 211 824 412 567 543 916 385 793 726 954 40 936 251 406 240 823 21 256 348 549 87 640 201 1102 445 748 377 511 619 863 299 685 343 386 1003 1012 229 843 498 1096 372 1124 834 880 443 570 284 896 669 1032 255 917 244 434 227 550 51 887 595 926 548 684 66 123 196 606 357 4…
Output: 277

Example 2:

Input: 345 3507 28 79 250 337 143 197 146 232 38 58 45 325 54 208 189 263 50 124 111 283 257 295 101 225 42 293 234 290 104 150 64 290 26 153 67 203 59 240 97 289 25 61 40 115 53 139 119 133 64 201 37 193 223 270 313 325 35 254 260 329 72 141 58 114 21 312 121 211 221 232 63 179 83 341 152 209 126 328 39 112 13 114 188 280 148 260 38 182 217 303 118 312 237 311 196 302 249 295 85 174 216 318 273 318 56 322 238 275 12 151 6 339 87 119 209 321 41 157 107 306 65 333 223 324 2 318 126 268 132 201 37 327 95 106 265 294 104 202 155 226 125 275 121 215 5 272 96 159 94 134 90 306 79 197 207 219 17 272 199 222 98 342 113 285 313 328 62 287 37 303 222 255 89 219 150 225 26 239 258 344 254 318 22 175 281 305 38 167 173 284 42 187 16 80 92 214 148 259 5 139 15 266 35 39 21 263 59 93 159 339 244 291 153 195 9…
Output: 1

Example 3:

Input: 1813 2993 550 1473 287 1382 449 538 1128 1643 532 1122 177 1516 33 1610 708 1537 308 365 297 1344 1237 1650 1123 1389 922 1364 38 1374 267 1523 621 1754 513 591 17 1468 520 1542 111 552 202 682 3 1653 411 507 418 1424 199 705 131 1347 482 1363 782 917 488 1167 662 729 202 1589 215 1459 1762 1763 832 1772 1245 1747 829 855 816 840 307 709 1433 1642 653 1774 569 1149 260 1354 628 976 601 1278 72 106 763 1508 126 1123 144 674 1288 1783 354 741 764 1005 330 703 477 1207 904 1287 620 657 1381 1538 43 402 962 1229 1211 1534 119 1577 631 1422 1227 1685 1386 1560 14 692 243 1107 299 618 491 1291 897 1413 1073 1530 241 1314 637 805 74 622 594 1121 756 1381 254 633 419 801 644 1192 399 618 329 1177 688 719 501 887 264 882 2 1775 961 1323 190 1156 618 673 456 1436 109 1438 1458 1480 586 1550 807 1644…
Output: 81

Constraints:

1 <= n <= 2060; 0 <= m <= 4120; 1 <= u,v <= n.

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