CT30358

Sara's Frosted bridges

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Sara the store warden watches over the port of Emberfall's stores of bridges. A careful computation stands between order and chaos. 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 <= 1178; 0 <= m <= 2356; 1 <= u,v <= n.

Example 1:

Input: 584 140 269 541 68 108 29 278 289 566 62 75 52 178 56 382 8 110 146 468 228 485 127 382 143 524 27 157 222 246 127 501 112 412 23 408 205 452 26 141 17 422 6 31 81 251 84 155 202 454 135 153 309 516 223 309 416 485 450 557 397 541 139 497 8 272 432 559 337 475 33 447 253 429 17 287 398 535 118 511 172 217 380 490 457 523 256 378 53 241 14 96 114 519 198 298 67 418 8 319 31 543 407 452 212 579 390 403 159 322 272 475 301 511 267 431 60 294 115 410 385 437 188 224 17 541 135 320 177 264 326 569 290 318 81 219 165 325 436 455 248 501 366 469 424 468 145 298 91 150 136 532 404 548 283 421 90 91 190 448 37 424 334 364 168 309 319 433 194 385 72 429 49 515 170 376 175 447 46 550 192 466 95 378 424 425 166 413 284 292 39 306 207 400 172 346 33 443 195 241 111 456 225 492 236 386 271 396 150 447 2…
Output: 444

Example 2:

Input: 242 354 58 80 66 189 77 239 133 169 162 214 33 103 16 138 75 201 85 169 24 146 27 61 14 209 113 158 111 164 238 242 32 222 173 203 100 189 143 159 180 201 50 206 32 193 49 68 84 92 5 189 70 194 20 26 74 215 30 48 107 118 160 174 50 139 1 29 126 193 49 131 5 194 161 177 137 150 169 224 151 202 84 106 184 239 93 222 110 205 122 136 131 157 30 195 98 231 108 141 48 81 6 172 85 109 75 124 7 170 60 157 16 94 51 79 147 165 96 196 23 48 92 109 79 110 160 189 40 193 125 201 81 134 63 184 35 212 2 212 179 192 59 109 178 188 44 74 47 230 54 127 34 52 113 139 148 220 70 93 97 193 20 58 58 118 66 209 1 101 81 182 96 216 167 221 64 215 50 204 7 53 3 182 117 122 125 238 12 147 87 199 104 156 124 207 124 202 7 195 120 214 44 122 85 206 120 211 34 108 123 196 2 167 215 228 220 223 72 199 147 157 38 55 201…
Output: 15

Example 3:

Input: 612 1852 228 298 495 500 431 438 201 563 74 458 185 328 143 279 189 507 112 551 133 558 266 499 111 551 287 387 109 537 326 514 23 316 118 251 34 242 222 518 251 499 207 314 553 588 165 596 125 180 254 487 329 407 194 336 396 558 423 477 424 606 139 440 512 566 149 595 419 578 461 603 162 601 141 417 10 223 514 521 136 277 110 228 17 594 221 413 565 572 82 259 27 595 30 108 119 195 13 202 38 404 19 288 317 487 351 542 88 396 436 533 181 222 39 103 216 422 18 521 271 312 26 594 184 216 449 459 42 398 373 610 9 232 401 514 7 175 17 608 22 120 471 497 85 538 405 480 416 586 351 523 38 178 364 416 362 433 181 562 184 347 76 584 127 281 42 305 131 292 103 270 239 445 251 519 40 328 49 481 33 343 76 401 203 356 66 133 129 526 342 429 134 510 229 442 245 472 229 522 534 550 274 504 289 589 291 41…
Output: 1

Constraints:

1 <= n <= 1178; 0 <= m <= 2356; 1 <= u,v <= n.

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