CT53188

Tara Counts the bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The surveyor Tara has been asked to schedule the next expedition. On the desk lies a long table of bridges readings. 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 <= 2740; 0 <= m <= 5480; 1 <= u,v <= n.

Example 1:

Input: 2439 1904 303 1898 986 2270 1337 2157 96 511 95 1668 226 1526 219 265 1543 1801 347 1673 205 2156 1092 1307 1197 1601 130 397 2040 2173 1322 1785 81 1866 1322 1782 544 1563 147 1409 2159 2256 1118 1908 38 1364 929 1517 795 1009 516 2224 660 2107 497 1380 530 1220 843 993 632 757 992 1580 653 1317 1264 2311 163 2227 955 2158 468 536 1637 2159 2139 2420 476 595 602 1463 503 1573 1127 1624 1825 2250 929 1152 382 1995 1550 1789 1304 2193 693 1466 24 1922 142 2336 1773 2279 438 1523 1896 2325 118 2244 700 1443 68 1235 264 2105 1798 2413 120 1108 233 2137 390 984 281 308 882 1160 351 538 1376 2129 1832 1975 35 49 15 2420 211 2207 184 1240 24 1097 421 2077 286 1303 1692 1974 1562 1721 86 2081 679 2323 1852 2184 1244 2058 365 2431 574 888 608 1618 790 1279 743 987 2100 2348 1593 2129 1317 2288 169…
Output: 665

Example 2:

Input: 1820 3717 212 1691 439 917 350 1250 996 1367 1096 1378 312 411 651 1034 928 1186 111 1218 73 358 567 1419 837 887 706 844 710 1058 327 818 945 1291 459 1253 143 921 694 883 1137 1211 274 1707 1313 1700 337 663 727 1034 243 1623 960 1208 238 1818 728 867 1619 1632 752 1034 1021 1621 190 1203 433 1420 300 332 293 705 101 1512 66 730 790 1548 297 372 493 1470 955 1724 244 817 479 1003 699 1552 778 1530 856 1047 517 659 1088 1098 652 1407 580 1690 706 1717 783 1396 77 1307 1016 1726 1359 1670 587 1661 520 1293 235 343 938 1132 564 867 166 905 213 944 334 1699 1029 1704 741 1384 1145 1409 924 1572 320 578 1080 1419 939 1038 842 1568 412 766 461 602 720 1049 798 974 468 1787 879 1660 666 787 1326 1413 288 361 1149 1245 1609 1706 597 1384 980 1642 591 1669 246 282 728 1748 427 1306 173 1401 552 9…
Output: 32

Example 3:

Input: 1889 1955 1134 1335 847 1209 160 257 154 1564 385 1157 88 1002 376 1012 1194 1511 1555 1868 691 1343 1041 1146 465 1196 380 1674 1402 1885 2 328 1749 1773 452 612 1436 1608 78 1347 1249 1396 415 1289 1000 1570 778 1397 361 1681 619 1212 410 835 1051 1094 491 1784 475 999 18 1315 178 1396 1189 1557 642 921 547 1492 334 901 505 928 578 1354 42 777 1248 1510 1094 1365 1050 1776 70 1534 61 997 436 908 66 915 441 805 426 1472 229 1449 995 1430 585 898 730 819 718 947 934 1054 1514 1697 449 533 909 1714 1667 1680 283 1174 1380 1394 395 1068 335 1062 827 1063 717 1181 622 1575 146 1823 1277 1503 718 1764 668 1254 609 1026 185 1727 71 855 1133 1315 542 799 175 979 1265 1528 169 412 168 686 1443 1682 809 1011 702 1296 1312 1886 1261 1281 1431 1816 207 274 937 1757 179 1663 1120 1588 297 694 239 388…
Output: 291

Constraints:

1 <= n <= 2740; 0 <= m <= 5480; 1 <= u,v <= n.

Loading...
Test Cases:No test cases
No test cases available.
Tara Counts the bridges - MEDIUM Coding Problem | CodeTikki