CT45446

Last canals of Mira

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Mira inherited the kiln at the savanna camp of Amberplain along with its curious bookkeeping system for canals. Time to make sense of it. 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 <= 3092; 0 <= m <= 6184; 1 <= u,v <= n.

Example 1:

Input: 89 497 2 42 7 59 60 79 43 53 28 64 46 57 43 50 4 54 24 82 42 75 61 83 3 72 21 48 64 83 6 35 32 70 46 49 40 58 12 45 9 53 12 78 4 14 16 18 11 33 21 62 5 52 9 63 41 62 12 55 37 59 6 38 3 63 43 79 37 62 20 60 12 51 4 64 1 89 41 42 26 53 40 71 18 29 17 38 12 73 16 73 36 62 5 12 32 54 42 80 20 32 20 56 23 79 2 82 38 56 11 79 6 42 9 77 1 63 82 84 9 15 50 66 33 60 2 52 53 62 37 79 12 81 35 58 31 46 68 80 13 16 6 23 32 87 22 69 41 64 5 88 25 48 42 43 29 82 44 50 14 71 24 85 33 76 11 74 5 27 34 66 14 25 51 83 23 76 11 24 66 71 60 69 11 53 5 30 36 56 23 32 20 77 62 82 5 45 32 57 24 49 24 64 11 70 53 83 24 47 50 65 4 49 17 21 53 64 12 67 59 81 27 41 41 82 50 76 20 33 65 76 28 61 29 57 39 54 6 59 57 69 39 87 18 53 7 43 30 36 14 57 36 86 50 84 75 78 49 87 54 68 6 33 7 80 14 17 25 39 18 61 4 10 20 35 31…
Output: 1

Example 2:

Input: 1833 290 476 1555 683 1539 445 1437 1 27 358 1483 152 1686 151 414 572 1022 17 1616 939 1064 820 1745 649 1391 177 619 90 1671 684 1082 953 1648 960 1459 607 846 74 579 148 1751 1141 1499 152 640 952 1136 376 1552 46 638 435 786 450 1699 127 1688 829 1347 180 977 20 709 723 949 664 1263 32 169 899 1200 959 1118 1415 1584 369 1568 77 948 1035 1186 265 1137 665 1753 75 139 610 1433 1390 1598 1021 1023 465 814 1815 1819 775 1347 367 409 346 1488 1130 1567 169 1523 102 1356 387 1148 1541 1770 1268 1404 186 645 132 804 1423 1737 318 729 672 1639 426 1353 756 1765 774 1069 292 1318 324 493 561 1349 579 777 136 516 80 1625 276 1828 455 530 1715 1812 289 746 487 1237 335 517 74 1455 221 315 784 1828 535 708 639 1643 163 596 1408 1536 364 1235 165 370 59 1275 1059 1667 28 537 483 1635 114 579 674 1…
Output: 1543

Example 3:

Input: 2175 5618 1980 2171 356 1065 713 1024 683 1803 874 1102 79 1203 1647 1758 1000 1852 158 1859 1382 1750 1732 1844 709 1456 1811 1957 97 871 898 2105 67 1454 1310 1471 320 1368 724 1483 1566 1729 403 734 397 1032 2049 2063 1039 2131 468 496 832 1774 893 1289 942 1415 86 1234 829 1953 180 2000 1506 1678 313 1711 942 1955 924 1758 989 1637 10 792 713 2068 295 1204 158 551 472 1660 761 2004 960 970 1426 1792 529 839 1955 1982 6 1432 392 2147 332 1349 159 280 1460 1767 1118 1653 63 1045 1595 1654 1638 1687 1853 2035 229 2173 1472 1524 686 873 142 781 20 1388 452 1455 315 1007 224 645 684 2171 901 1702 158 1495 517 1512 446 1963 425 1787 1621 1953 491 833 397 1157 14 1632 875 1114 196 1719 517 1809 734 1261 34 1890 678 1669 1575 1967 698 1899 911 1031 519 1171 73 78 984 1615 223 1902 793 1567 656…
Output: 14

Constraints:

1 <= n <= 3092; 0 <= m <= 6184; 1 <= u,v <= n.

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