CT44954

The Dusky tunnels of Piper

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the indigo vats of Bluehollow with crates of tunnels, and Piper the ledger master must account for every last one. 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 <= 1562; 0 <= m <= 3124; 1 <= u,v <= n.

Example 1:

Input: 688 431 170 289 245 446 51 335 427 429 410 544 415 475 3 637 28 138 64 650 207 625 16 506 498 576 334 382 206 416 93 154 40 61 70 684 200 388 243 435 104 538 211 281 16 193 84 181 275 383 200 371 56 104 96 685 87 395 622 669 304 516 103 262 265 274 312 585 221 253 232 482 64 342 384 636 170 628 378 421 30 649 456 495 441 662 138 217 7 52 29 418 15 56 373 425 26 438 106 631 275 292 484 594 293 619 267 673 57 147 288 658 436 491 231 575 352 623 599 670 317 651 202 453 447 501 238 535 120 313 514 650 116 342 235 415 83 425 127 544 427 567 273 604 163 607 565 683 223 604 113 634 430 478 203 488 317 600 285 323 341 393 67 606 101 381 431 458 38 425 64 427 316 576 36 221 100 392 148 214 235 479 408 648 273 441 246 264 84 329 431 677 670 684 382 523 141 426 96 236 74 97 248 531 22 546 198 350 449…
Output: 261

Example 2:

Input: 1451 641 470 618 137 448 414 549 645 854 228 1442 171 282 148 1289 980 1048 816 1263 469 832 858 903 603 1131 97 1416 985 1296 1409 1440 233 440 375 913 8 226 72 136 807 979 117 529 152 367 764 1409 1105 1365 398 579 342 355 465 713 764 1102 609 881 164 267 560 908 36 768 281 472 316 1110 988 1289 349 1430 842 974 163 460 503 664 748 782 396 1183 438 453 198 960 960 1440 493 1368 217 1303 227 1062 1294 1323 352 1410 470 1335 389 1354 570 1037 157 573 59 973 860 1137 625 791 95 220 735 1086 14 312 185 441 125 1034 161 598 811 1256 801 811 510 1114 1160 1307 867 1053 351 1277 449 672 1136 1443 835 1287 781 1147 427 1007 828 1172 353 864 159 1090 862 1088 764 1404 1154 1269 490 905 407 1166 720 1367 272 1294 20 311 502 787 461 536 1233 1442 237 339 467 514 641 1232 434 1023 551 686 458 888 52…
Output: 810

Example 3:

Input: 676 1120 163 488 87 601 55 401 429 665 55 533 177 551 270 662 244 612 382 393 146 180 93 626 401 459 58 208 103 387 201 432 320 432 335 413 342 496 163 283 426 477 596 620 84 325 187 519 543 605 75 378 82 586 437 569 31 234 28 238 412 551 36 535 1 536 299 524 190 297 140 404 258 314 104 479 76 134 8 168 483 665 451 543 168 431 316 460 302 600 112 666 119 137 144 367 106 390 123 445 471 528 334 442 202 471 448 498 1 261 103 426 142 598 82 271 328 447 55 498 379 598 220 429 74 277 95 144 10 56 58 106 601 639 93 622 256 373 216 440 380 392 231 255 599 601 137 248 30 162 374 598 472 543 266 593 583 632 496 615 230 388 254 455 405 433 369 452 190 443 265 577 214 399 217 511 87 138 408 568 486 640 241 407 55 596 411 559 151 262 125 580 193 425 234 362 227 334 335 613 444 613 20 279 40 579 354 47…
Output: 31

Constraints:

1 <= n <= 1562; 0 <= m <= 3124; 1 <= u,v <= n.

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