CT43103

Hans Counts the roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the moonlit lagoon of Selene. Hans 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 <= 2435; 0 <= m <= 4870; 1 <= u,v <= n.

Example 1:

Input: 852 1929 208 789 62 479 183 646 228 714 131 520 468 612 362 374 631 781 282 304 371 762 682 785 725 803 173 436 214 230 248 368 291 490 277 386 119 404 188 658 397 476 488 673 369 684 238 348 690 809 500 603 398 409 502 595 220 385 498 698 105 374 543 714 281 580 562 651 50 497 65 215 175 416 265 736 34 366 231 761 106 271 407 809 574 734 284 655 63 292 34 741 390 591 87 170 163 655 78 784 229 507 284 602 15 734 561 762 646 732 63 804 321 326 37 336 71 452 575 708 292 470 88 319 172 295 510 618 425 501 134 618 213 252 253 595 174 779 48 145 60 631 201 662 3 322 19 240 324 343 181 823 135 324 153 394 196 237 54 87 160 397 420 632 108 189 837 849 33 255 474 684 38 93 80 242 712 807 129 513 35 182 292 646 123 275 141 591 83 432 41 349 11 501 382 834 183 748 609 641 83 845 39 813 82 315 479 77…
Output: 17

Example 2:

Input: 352 2515 61 271 86 186 56 88 131 167 313 335 205 237 102 349 228 350 16 51 86 129 30 309 179 216 261 318 96 229 167 236 15 352 148 211 279 308 254 324 234 290 150 172 54 228 205 251 70 142 62 346 27 58 68 281 326 333 199 321 36 173 87 164 178 261 34 67 7 343 131 185 329 350 203 308 51 168 77 331 14 95 53 117 110 341 225 295 92 186 67 165 194 327 227 272 23 45 192 295 194 261 95 342 170 257 142 240 287 329 14 113 232 272 201 285 64 264 167 314 48 294 200 274 43 238 145 325 94 286 175 285 76 142 199 209 256 258 164 270 108 230 13 117 183 334 203 275 181 348 99 282 194 330 246 295 20 121 247 269 273 342 75 119 116 351 56 284 26 269 166 213 112 211 1 239 166 229 42 258 250 347 19 108 13 344 88 328 11 250 139 238 232 348 70 224 105 282 262 301 26 276 148 174 170 301 146 265 94 328 101 279 77 12…
Output: 1

Example 3:

Input: 1749 1744 694 1145 1287 1533 591 1017 239 1706 167 1062 1344 1663 380 1011 278 972 311 1351 153 1036 361 1070 167 1050 1131 1234 419 1600 684 1340 219 301 952 1382 855 1515 741 878 635 1626 211 1305 390 626 708 1744 63 198 826 1521 1297 1423 569 1096 734 1700 1075 1094 483 1334 1500 1706 112 1511 974 1034 1074 1233 848 1129 378 584 654 1430 1193 1334 1 1451 424 866 929 1642 336 1057 1090 1618 1271 1343 1155 1443 328 488 103 1176 196 1693 226 461 376 1732 6 1241 109 341 290 1580 793 903 1009 1140 449 1653 106 1716 729 823 360 1094 265 436 562 1506 1190 1593 744 1579 146 330 700 1244 505 761 833 969 885 972 1298 1603 652 1287 77 1269 1021 1045 78 595 97 238 1076 1601 436 1060 313 989 770 1732 6 1557 589 1290 1035 1370 957 1171 320 1324 912 1622 147 1701 861 909 1587 1663 532 1083 1115 1245 3…
Output: 261

Constraints:

1 <= n <= 2435; 0 <= m <= 4870; 1 <= u,v <= n.

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