CT42474

The roads at Sandspire

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the desert outpost of Sandspire, Opal the surveyor keeps careful count of the roads. Verify the ledger before the auditors arrive, every figure matters. 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 <= 1174; 0 <= m <= 2348; 1 <= u,v <= n.

Example 1:

Input: 886 2062 543 612 466 469 474 799 30 248 502 759 254 439 485 695 166 425 491 617 285 850 407 879 126 440 598 883 714 782 314 677 32 588 63 601 20 467 327 361 60 341 206 749 11 168 165 714 571 865 19 367 365 542 156 171 281 507 373 850 623 666 495 742 148 592 351 626 187 704 50 568 411 731 52 854 247 797 713 879 521 767 53 470 686 834 160 412 354 476 143 486 20 531 253 397 424 687 395 801 536 870 408 410 359 833 744 780 58 422 69 262 595 681 78 751 334 456 144 738 52 738 395 446 79 424 350 405 212 360 280 402 261 795 151 263 305 592 55 724 221 429 301 392 765 781 531 616 190 580 387 865 111 417 78 822 439 714 460 576 339 581 300 367 283 820 7 758 180 725 4 52 111 655 99 353 778 802 391 556 185 486 30 632 92 420 154 707 168 844 412 521 311 396 287 491 51 136 218 362 432 750 121 228 291 354 26…
Output: 9

Example 2:

Input: 903 1014 289 419 629 871 383 616 346 805 206 791 50 219 582 719 169 851 129 521 498 732 286 340 145 159 768 848 275 793 321 331 120 636 560 841 319 403 168 176 96 626 113 770 34 485 592 756 232 340 20 369 344 815 220 478 132 737 231 343 737 885 829 903 591 886 552 650 229 499 393 398 75 347 135 195 13 153 316 636 272 571 552 798 435 734 142 208 2 646 183 190 240 758 369 410 529 836 202 802 103 313 424 859 168 899 31 769 70 115 348 512 298 560 15 236 39 590 346 629 166 342 415 605 116 227 51 396 89 567 46 481 449 720 96 813 232 616 159 673 570 625 117 145 325 838 486 655 119 259 659 720 476 663 49 807 275 837 36 651 3 465 63 341 20 276 274 418 193 435 657 737 529 606 141 408 235 484 573 588 478 806 215 709 471 526 458 575 36 93 394 414 333 612 530 834 157 609 318 578 745 753 262 433 222 270…
Output: 122

Example 3:

Input: 277 1924 37 77 255 266 74 137 127 247 194 270 101 145 56 271 221 259 218 276 16 249 15 218 66 74 149 244 101 167 22 164 211 247 82 125 10 246 24 88 91 129 114 222 7 244 97 150 118 204 23 199 153 188 95 180 114 243 29 253 200 232 200 258 14 218 118 126 51 250 57 167 34 190 87 168 93 185 3 116 58 195 7 146 28 49 2 52 24 130 125 206 70 257 261 272 51 219 106 222 168 245 95 131 30 233 136 166 44 130 104 126 224 235 180 189 172 241 218 232 45 142 30 70 21 201 138 252 246 265 59 270 199 229 98 245 212 236 30 172 145 163 139 260 193 217 142 153 274 276 148 233 4 165 169 273 21 273 107 122 107 193 135 217 4 60 212 269 15 76 42 45 61 81 149 220 91 160 51 263 217 224 84 174 145 228 100 183 4 191 153 219 18 173 95 195 179 239 47 246 166 264 17 77 63 223 11 47 60 152 66 269 72 163 84 155 253 275 3 265…
Output: 1

Constraints:

1 <= n <= 1174; 0 <= m <= 2348; 1 <= u,v <= n.

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