CT36056

The bridges Separate Camps Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the obsidian flows of Blackglass opens only for a perfect tally of bridges. Peddler means to find out. 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 <= 1451; 0 <= m <= 2902; 1 <= u,v <= n.

Example 1:

Input: 1077 932 205 1014 697 924 241 1057 15 352 90 721 869 1000 263 490 420 488 79 532 476 869 49 652 597 889 41 994 215 454 182 707 18 1008 66 301 691 773 583 960 620 967 477 982 126 717 221 719 491 954 161 404 372 540 462 583 144 566 657 683 209 251 72 919 1016 1026 58 292 377 926 194 602 985 1064 32 476 555 591 87 986 53 66 96 637 546 1047 729 822 312 333 95 99 911 971 763 1009 328 407 607 688 214 946 181 347 397 441 226 726 343 883 172 848 67 408 368 435 361 964 747 784 233 918 269 817 50 109 685 982 437 584 570 732 970 1057 25 1062 287 966 289 616 442 490 182 880 309 589 224 520 149 401 983 1035 225 935 42 583 329 716 466 1031 575 1013 86 247 645 1055 319 956 271 352 245 685 236 567 29 482 939 1002 366 496 561 1049 867 1049 242 1055 147 942 743 1010 183 363 657 859 132 956 80 995 249 401 28…
Output: 230

Example 2:

Input: 827 1559 396 520 150 653 181 401 337 768 613 763 526 719 22 547 426 508 358 807 102 699 71 547 299 817 700 768 119 370 178 236 480 500 91 270 353 381 448 719 102 542 570 630 649 802 258 745 97 608 178 784 506 508 6 696 171 514 418 782 32 517 127 331 82 682 694 715 668 717 150 602 291 743 206 319 93 399 174 334 273 415 495 520 75 714 382 586 367 769 213 455 271 350 131 221 19 472 157 319 175 353 230 561 316 581 221 249 347 528 155 502 350 510 27 773 363 407 78 323 609 672 306 773 387 619 80 602 319 531 566 795 331 384 46 769 79 216 50 373 86 757 492 610 601 811 228 488 27 500 587 645 72 188 281 568 123 313 13 155 176 236 346 470 613 783 267 672 424 680 159 257 565 567 116 168 194 707 181 637 340 587 347 814 188 362 518 583 73 696 32 492 480 549 25 249 92 305 276 402 266 466 13 741 299 495 6…
Output: 22

Example 3:

Input: 414 673 175 278 54 89 220 265 268 280 108 391 82 212 98 325 111 278 254 388 70 263 195 382 43 209 63 409 102 266 4 373 215 233 165 374 72 301 19 182 42 93 118 271 163 332 399 402 201 328 85 404 73 172 97 323 1 221 265 346 151 404 290 397 107 124 389 390 132 133 171 284 156 306 58 365 67 356 38 290 9 321 195 347 7 226 43 187 279 408 70 252 105 329 332 339 52 152 87 289 111 368 25 322 160 315 140 150 256 330 98 275 8 237 121 312 151 353 47 367 109 222 21 101 57 343 154 307 10 73 338 354 121 382 49 271 310 337 130 216 29 357 364 390 179 183 32 403 234 343 2 133 95 402 379 410 126 338 286 395 206 242 205 307 298 404 34 66 96 361 27 170 29 260 128 137 235 286 308 319 229 297 182 221 20 208 245 395 14 18 237 311 189 382 121 270 92 118 9 283 306 312 177 297 287 332 43 74 110 335 72 77 18 126 33 2…
Output: 23

Constraints:

1 <= n <= 1451; 0 <= m <= 2902; 1 <= u,v <= n.

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