CT46272

The bridges Separate Camps Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the copper works of Verdigris, Admiral records each bridges in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2387; 0 <= m <= 4774; 1 <= u,v <= n.

Example 1:

Input: 1996 1342 907 952 365 1612 417 950 835 1166 406 1546 235 1643 892 1786 311 1435 1089 1268 486 1493 1131 1459 185 1335 1565 1805 667 839 453 1851 446 1085 1156 1198 849 1765 1671 1992 128 741 534 1941 190 1166 300 1948 260 1835 491 1487 483 947 678 1725 1559 1619 110 899 1418 1528 716 1757 743 1673 193 1728 167 701 875 1993 657 1889 1273 1426 399 1452 138 1786 125 1644 471 1871 187 1362 328 1679 1279 1762 689 1505 609 1587 72 1863 543 1394 603 1026 658 811 1205 1636 773 1154 1289 1628 1171 1557 133 1454 892 925 1243 1310 1280 1694 1419 1593 419 1662 375 1229 985 1613 367 1729 241 1482 518 1104 765 1033 300 755 246 386 288 569 254 1712 56 501 159 1719 412 1102 1541 1788 101 1224 482 688 1954 1982 457 1237 673 812 5 1387 968 1281 591 625 216 1435 1145 1670 933 1778 199 854 263 760 233 702 151…
Output: 686

Example 2:

Input: 437 3041 239 252 42 399 16 79 107 379 99 169 257 372 190 360 153 366 376 428 63 312 63 249 240 257 113 146 113 239 345 403 54 259 18 276 109 123 286 367 251 387 39 187 80 432 56 210 395 426 133 432 19 344 242 423 101 236 131 139 147 232 32 176 28 33 212 355 6 177 91 114 82 180 169 225 32 61 172 368 104 204 308 332 295 356 252 382 21 365 76 317 177 333 257 342 55 274 16 122 99 118 196 386 140 421 98 339 257 315 242 361 142 307 144 262 143 153 101 155 295 369 104 215 38 189 16 258 111 240 344 347 16 191 153 418 399 425 239 355 109 195 159 258 238 355 2 372 329 354 49 352 25 114 125 350 61 245 71 82 102 246 53 359 200 426 154 228 157 349 224 287 159 321 34 44 344 349 43 268 71 260 177 266 154 164 285 384 142 272 377 424 216 324 222 256 143 388 38 106 102 205 297 306 90 333 79 207 66 342 180 3…
Output: 1

Example 3:

Input: 1936 988 1096 1183 258 1380 530 1540 986 1271 18 979 60 1370 993 1598 116 159 218 1585 1131 1570 184 1772 354 1295 694 1554 414 800 354 748 956 1225 401 451 1370 1382 1014 1655 416 1238 352 1879 124 346 409 1109 841 1932 331 1148 1253 1798 1065 1619 1103 1531 509 1916 93 1368 781 1831 535 918 158 198 206 1098 907 1008 881 1435 1549 1778 1244 1698 1283 1607 443 774 518 1820 947 1733 413 1326 303 695 431 522 16 540 273 1192 1652 1763 382 1522 754 1645 1234 1494 759 1710 954 1708 330 1321 176 279 27 1092 903 1696 378 1546 255 1393 323 574 588 1180 15 952 1012 1875 587 1625 187 1783 331 1353 321 1394 197 313 1521 1568 1004 1429 1262 1785 277 1202 332 571 649 1077 382 1757 963 1336 142 177 76 763 416 804 367 1047 1849 1882 225 1487 834 994 971 1459 586 1650 343 1598 790 1759 46 766 1438 1858 24…
Output: 950

Constraints:

1 <= n <= 2387; 0 <= m <= 4774; 1 <= u,v <= n.

Loading...
Test Cases:No test cases
No test cases available.
The bridges Separate Camps Puzzle - MEDIUM Coding Problem | CodeTikki