CT48336

The roads at Scriptoria

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the ink district of Scriptoria, Nils records each roads 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 <= 2038; 0 <= m <= 4076; 1 <= u,v <= n.

Example 1:

Input: 594 3914 163 172 227 592 50 151 59 217 28 148 326 534 29 296 316 428 7 316 44 260 101 539 10 442 76 316 65 233 161 510 96 322 7 421 179 199 116 546 62 367 182 318 321 582 24 509 115 437 229 322 194 242 113 458 74 531 455 490 201 418 35 298 55 439 182 392 321 589 367 515 111 319 28 33 302 396 236 247 85 447 415 481 22 104 473 519 342 464 136 293 39 169 77 218 342 542 141 556 327 387 426 469 99 272 23 223 169 505 270 584 396 448 270 426 381 569 135 207 397 501 376 500 74 390 334 594 40 592 210 528 59 209 259 365 169 358 185 347 319 573 210 302 194 565 280 378 292 522 38 581 108 164 268 418 299 302 312 411 388 547 374 565 398 573 29 438 7 228 539 591 58 249 437 489 455 550 254 266 245 579 89 517 499 539 36 97 229 582 456 474 360 391 254 354 72 429 110 447 247 275 50 421 147 473 84 150 395 571…
Output: 1

Example 2:

Input: 1930 3201 616 1530 437 1056 1189 1278 830 1178 687 1617 1209 1731 868 1569 1113 1849 1608 1745 138 827 751 1012 251 1123 100 1509 102 604 502 1298 132 958 198 1408 134 1457 968 1894 55 690 123 306 1495 1533 1428 1893 968 1410 289 559 113 1195 148 757 518 1872 371 1118 404 693 844 1713 94 208 817 1870 988 1534 50 514 265 839 469 1268 415 1739 167 1027 426 1084 57 1544 808 1170 692 1859 822 1271 90 1083 838 1524 385 934 859 1071 1276 1648 31 923 498 1553 271 1583 736 1740 256 596 866 1530 1200 1690 703 1777 267 1349 664 1347 345 1289 707 795 1716 1836 3 981 582 981 381 632 534 1065 199 1120 307 1881 132 1191 738 1337 1313 1464 1012 1371 946 1569 128 1305 940 1069 1663 1698 330 1874 715 1594 1644 1697 881 1307 878 1368 381 832 524 1338 1578 1835 27 1531 756 888 529 1093 1178 1488 1376 1624 89…
Output: 67

Example 3:

Input: 330 424 125 169 164 173 21 275 153 324 182 258 212 232 122 146 192 245 148 322 283 318 56 98 8 191 117 251 291 321 47 154 71 152 131 203 79 167 135 258 112 255 199 317 20 34 74 300 56 78 172 273 5 248 126 171 10 235 135 153 52 293 7 274 17 249 54 148 47 243 118 276 5 123 2 115 159 324 5 225 195 213 1 126 256 325 45 282 231 271 185 282 258 314 252 325 99 309 125 321 92 148 94 151 25 196 22 178 237 301 43 261 120 286 261 279 94 125 105 225 31 94 79 139 84 325 62 251 113 225 73 170 100 258 7 56 25 122 75 227 164 292 197 237 66 82 85 281 155 195 55 152 92 303 87 91 15 320 85 252 203 243 22 299 94 113 146 199 301 308 154 294 86 182 61 263 105 178 108 159 233 264 208 253 280 292 96 298 67 251 234 295 145 185 200 328 235 258 132 175 33 198 120 182 28 242 73 290 109 244 20 226 278 281 64 258 126 2…
Output: 38

Constraints:

1 <= n <= 2038; 0 <= m <= 4076; 1 <= u,v <= n.

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