CT29534

The Starlit tunnels of Rune

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Rune found an old ledger of tunnels in the apothecary attic at the lotus ponds of Tranquil Basin. The margin notes pose a precise question. 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 <= 1809; 0 <= m <= 3618; 1 <= u,v <= n.

Example 1:

Input: 1730 363 394 1247 1520 1668 425 1533 488 636 772 1027 1179 1312 359 1584 397 1320 462 1299 1299 1343 950 1574 443 590 120 1665 646 721 264 721 38 728 526 1329 504 1514 253 1382 1296 1468 24 1036 655 1635 198 320 351 425 1191 1545 29 237 860 1539 680 1524 404 1588 60 1396 200 1280 177 1064 447 1223 670 694 817 1275 622 1613 482 995 480 1730 833 909 1047 1432 738 761 1243 1404 271 984 36 853 206 864 244 1196 539 1177 430 1552 310 1357 1222 1539 401 1383 25 1226 908 1190 339 1344 1179 1706 95 201 489 864 363 1577 59 152 197 474 171 274 605 1213 530 1590 690 1152 305 1146 1068 1159 957 1034 33 301 1141 1627 427 584 753 1387 179 297 746 957 1303 1633 815 1153 629 1224 530 569 1701 1720 729 1486 354 613 480 856 145 711 368 402 12 303 754 1665 930 1092 743 1635 282 1647 588 649 508 994 837 1125 5…
Output: 1367

Example 2:

Input: 805 2648 154 786 301 630 214 697 207 781 133 160 268 745 220 765 551 566 658 702 184 477 246 327 367 392 302 578 422 675 140 571 46 164 335 457 20 629 307 724 72 425 320 491 225 494 276 569 120 801 178 737 538 707 535 705 205 314 25 74 93 454 293 704 207 787 631 632 277 522 573 704 188 207 208 402 154 733 63 134 301 530 600 670 17 736 210 663 255 517 36 282 84 115 723 768 499 603 4 122 338 584 319 706 155 435 99 309 292 632 302 314 76 451 583 801 330 504 235 338 537 794 44 535 590 763 247 372 57 528 270 371 535 540 103 313 268 280 57 544 227 425 139 649 235 241 407 672 388 689 50 613 18 26 338 525 32 451 19 472 99 382 144 747 265 514 603 710 143 224 287 339 269 779 275 730 1 648 370 382 22 80 89 363 288 686 48 64 91 480 242 608 385 614 113 157 32 371 592 604 171 778 198 660 370 481 236 583…
Output: 1

Example 3:

Input: 1464 698 28 743 359 958 224 1138 222 1197 430 845 92 235 565 1105 434 1173 85 1250 497 860 1092 1188 594 746 252 369 323 1300 863 1052 85 473 73 1304 1282 1340 843 861 315 1100 80 1413 214 901 137 1167 428 1204 417 919 226 575 189 835 762 1095 393 943 92 979 435 1369 632 1085 111 502 252 1384 338 1228 1275 1445 758 759 698 907 451 1303 575 1345 194 1028 69 877 249 1160 138 251 1019 1226 901 1258 426 644 179 1366 142 344 465 1207 208 527 904 1041 1219 1284 805 1310 724 1027 481 1022 394 1411 113 1067 381 392 69 280 356 1147 647 750 416 645 604 762 952 967 556 969 557 1354 400 516 549 1080 369 437 52 86 151 1326 878 1233 833 1332 794 1156 15 599 33 1348 799 1177 838 1113 1093 1360 280 368 1019 1321 622 977 737 1049 65 899 62 1432 827 1011 34 657 621 818 326 1125 273 907 736 1270 373 1247 962…
Output: 766

Constraints:

1 <= n <= 1809; 0 <= m <= 3618; 1 <= u,v <= n.

Loading...
Test Cases:No test cases
No test cases available.
The Starlit tunnels of Rune - MEDIUM Coding Problem | CodeTikki