CT45761

Faye and the Separate Camps

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The clerk Faye has been asked to secure the caravan contract. On the desk lies a long table of routes readings. 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 <= 1705; 0 <= m <= 3410; 1 <= u,v <= n.

Example 1:

Input: 1493 1699 291 347 48 505 1195 1388 295 913 860 1320 456 856 34 1405 25 887 510 536 530 1275 210 1422 701 1211 391 1335 235 1056 592 1153 133 1136 383 456 696 1444 306 678 673 1286 304 1232 821 883 1046 1459 80 1350 293 976 206 236 246 476 376 492 2 323 551 1125 758 1198 239 389 17 55 253 1451 391 1097 285 951 390 1062 147 864 947 1432 265 472 326 731 305 432 248 890 1221 1411 647 686 434 935 899 1357 521 646 370 1388 620 1012 861 1468 406 1136 778 1486 429 1190 932 962 424 475 346 1134 630 734 405 545 124 1392 479 1001 82 185 113 865 717 1492 1163 1417 627 1123 419 1331 1063 1377 163 1229 121 818 867 1231 22 387 193 580 142 1216 739 1306 293 1261 362 566 506 1195 289 1379 483 1468 1004 1308 152 977 441 861 850 1423 59 1415 402 1077 455 564 738 1176 350 1008 618 1034 820 1407 614 1349 1193 …
Output: 160

Example 2:

Input: 1515 1048 664 1154 967 1176 1032 1109 699 1152 776 997 568 1338 669 1357 93 574 360 1048 1323 1392 1099 1503 625 829 854 890 1080 1318 4 875 1288 1420 279 1435 697 762 319 1063 228 600 516 849 913 1495 697 1458 882 1312 51 521 1122 1326 333 848 759 1365 297 448 17 368 393 930 1266 1397 638 1249 930 1325 1127 1398 651 1190 249 878 47 915 1045 1227 954 1227 819 1344 752 1294 222 444 762 1483 90 216 34 1268 60 1437 171 1230 649 926 361 1337 428 857 828 1327 724 775 402 1202 617 856 646 1096 45 386 568 1108 276 1287 81 493 801 823 179 801 92 1031 315 429 444 464 406 567 825 1075 109 1264 522 993 865 1131 162 1317 684 753 471 1373 412 813 544 776 789 1343 817 871 68 102 318 508 54 1298 1034 1179 1087 1130 908 1188 1117 1436 120 218 319 893 485 1030 182 665 280 442 493 503 1098 1353 494 1193 193…
Output: 500

Example 3:

Input: 721 3155 289 325 10 35 14 257 343 372 50 631 543 596 82 605 91 221 21 465 583 588 99 664 295 367 249 532 169 579 286 421 247 703 434 469 72 233 101 102 344 360 167 596 159 478 54 107 430 487 571 590 179 242 216 559 197 333 428 640 139 425 134 244 390 495 325 668 183 590 44 543 239 358 172 383 537 565 248 550 74 155 63 707 190 316 171 284 190 215 231 416 202 458 79 81 617 629 103 347 125 297 475 590 149 719 267 383 96 172 98 609 412 458 280 581 166 697 469 495 5 268 65 417 439 689 56 168 374 464 87 486 117 168 418 519 7 249 143 485 87 192 46 683 16 460 204 456 3 686 40 508 363 569 232 383 85 655 29 341 340 375 168 223 186 654 413 427 26 457 546 649 483 653 25 124 40 102 351 367 467 599 24 62 276 469 69 624 88 231 179 641 323 357 275 580 324 589 287 531 377 525 112 632 135 293 345 497 104 35…
Output: 1

Constraints:

1 <= n <= 1705; 0 <= m <= 3410; 1 <= u,v <= n.

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