CT35097

Jarl's bridges Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the cotton rows of Whitewick close for winter, Jarl must finish the bridges ledger - one figure at a time. 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 <= 2268; 0 <= m <= 4536; 1 <= u,v <= n.

Example 1:

Input: 1572 2202 75 99 1154 1482 234 1429 700 825 763 992 736 1015 652 1415 585 900 485 716 68 1123 9 1322 101 604 102 1252 299 464 284 1092 3 1308 1002 1363 240 1347 172 186 526 1264 697 1316 891 1507 478 1118 1034 1373 188 238 614 675 500 524 388 908 605 830 1168 1441 239 254 770 1511 924 966 571 1346 168 1196 754 890 467 1016 766 1046 219 569 302 666 76 1187 196 211 178 1107 169 444 502 1330 308 1067 1058 1279 1022 1494 1003 1043 1024 1504 1063 1277 159 213 640 1401 514 851 385 1522 925 1056 527 1531 160 830 662 899 249 954 528 1394 620 650 342 1388 896 1345 806 1212 580 1271 1043 1561 484 1111 535 1015 993 1457 515 907 70 895 837 1205 134 1235 697 848 1022 1091 781 1204 229 881 802 1124 59 320 789 1245 392 760 484 734 413 1510 1358 1480 1232 1301 347 1084 268 387 423 1404 391 1205 396 889 101…
Output: 115

Example 2:

Input: 2208 3110 562 660 1260 1274 1398 2051 1072 1833 529 1061 1609 1930 194 466 501 1932 26 957 1060 1620 1627 2072 28 138 1279 2161 236 631 169 819 430 1683 315 1584 1458 1851 1033 1201 436 1857 169 401 1321 1942 93 339 1450 1573 340 591 1168 1372 1917 2092 486 709 453 873 14 275 402 1296 464 1762 704 2071 275 1884 620 1665 979 1806 210 321 138 1101 269 2089 1145 1349 636 680 1467 2101 133 608 743 1055 1724 1831 899 1991 421 1436 1083 1260 865 1820 618 1705 1263 1812 852 1636 907 1326 241 1505 77 426 1549 2199 808 2199 1003 1362 1826 2042 147 1944 1252 2194 18 1323 430 1676 138 2193 1738 1762 425 630 356 1816 66 1574 534 2031 811 1975 1582 1686 131 335 413 976 1286 1589 100 1131 317 782 1611 2180 1025 1396 787 2015 1255 1445 281 2062 22 441 130 1905 562 1906 695 920 346 600 123 621 237 1075 14…
Output: 138

Example 3:

Input: 772 3502 64 715 128 278 184 334 210 465 181 492 292 658 8 767 264 360 458 653 280 282 700 741 540 689 553 772 188 621 211 600 59 410 626 690 371 488 262 683 374 471 580 704 11 427 197 700 304 402 72 413 193 554 224 637 362 762 365 407 151 322 223 619 333 386 283 750 610 752 18 572 353 366 143 585 654 708 62 508 60 254 316 475 599 672 627 747 547 738 149 186 105 332 222 233 519 707 68 271 204 734 495 651 42 512 370 679 445 737 140 682 232 558 152 180 49 441 173 473 125 571 2 195 710 725 146 375 123 184 20 208 323 358 418 455 205 365 243 278 161 300 303 650 43 100 626 714 445 759 731 733 13 239 509 663 240 659 96 102 73 401 357 616 8 483 494 690 139 167 262 631 375 752 131 518 536 695 417 499 302 551 85 547 394 500 327 695 443 615 245 677 3 390 160 488 226 278 46 435 369 537 378 454 107 714 …
Output: 1

Constraints:

1 <= n <= 2268; 0 <= m <= 4536; 1 <= u,v <= n.

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