CT45171

Aria's Ledger of roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the beacon hill of Lantern Tor. Aria spreads the roads records across the table and picks up a sharp pencil. 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 <= 2701; 0 <= m <= 5402; 1 <= u,v <= n.

Example 1:

Input: 1263 3654 854 1100 407 1205 334 922 149 177 1073 1129 556 736 129 189 830 1240 384 898 20 221 367 1235 61 73 96 954 257 363 469 612 944 1043 836 903 262 898 866 1081 1021 1130 430 825 716 1045 408 900 131 306 777 1121 897 1046 127 752 235 379 347 473 85 571 157 672 592 925 222 1195 170 1236 9 964 122 702 973 1020 123 690 45 111 876 1212 925 1224 631 1055 852 912 590 1251 80 509 308 892 334 625 153 1135 334 1177 730 863 233 704 164 1230 528 695 32 292 323 1010 916 999 592 652 405 1164 281 633 506 1133 543 929 263 416 398 650 396 649 382 423 132 953 1011 1086 850 982 470 638 364 643 266 888 296 367 592 644 169 600 62 1092 174 1207 760 1104 809 1135 341 722 154 992 482 488 57 99 884 1255 3 658 369 498 199 1004 229 452 232 461 1049 1159 121 282 987 1208 196 1006 270 1236 879 1196 907 1078 168 …
Output: 5

Example 2:

Input: 73 1984 46 69 37 49 40 46 22 42 43 52 49 56 60 63 49 51 1 14 57 73 11 19 8 15 38 69 9 25 47 52 46 63 26 45 37 43 37 52 3 23 15 49 65 68 36 40 27 30 11 24 34 70 1 68 10 53 19 63 42 48 17 68 13 23 30 31 26 65 62 69 3 16 30 36 2 13 2 47 10 30 9 24 1 58 24 61 42 47 32 58 2 51 1 71 31 39 25 49 28 53 18 54 33 70 15 32 15 19 14 25 8 23 45 46 12 21 23 45 42 58 4 21 20 46 66 71 48 72 8 58 26 34 24 39 42 59 6 54 27 66 52 64 26 29 52 56 5 19 30 60 21 43 13 16 17 58 1 63 65 72 7 56 20 44 11 45 47 59 1 62 1 10 41 55 30 59 10 13 25 68 48 62 20 37 15 27 11 39 24 63 33 47 14 51 5 47 11 71 23 70 54 62 51 53 32 67 16 19 10 41 45 72 30 38 71 72 2 10 42 54 11 56 17 47 12 53 23 48 15 65 15 38 3 57 34 58 14 21 22 44 12 40 45 67 9 35 31 57 39 73 6 42 9 68 34 49 2 5 28 40 5 9 17 19 4 32 38 63 2 12 19 46 11 18 29 …
Output: 1

Example 3:

Input: 438 456 247 258 62 79 10 319 74 283 125 316 267 274 54 296 28 256 3 268 20 23 100 357 125 175 50 96 190 361 270 384 154 279 40 147 309 340 282 362 73 136 173 381 317 414 30 252 75 418 336 397 53 259 338 393 11 78 352 435 95 411 333 415 74 119 55 282 185 323 398 419 50 406 320 347 298 317 84 224 151 210 140 259 111 182 113 414 77 160 7 279 21 399 337 418 319 327 169 314 101 370 85 155 250 390 49 269 45 306 311 331 87 272 270 350 165 287 258 342 38 140 264 403 266 383 120 351 7 379 152 287 55 235 27 390 169 255 233 397 251 314 15 18 34 279 216 328 130 208 43 250 28 226 88 135 93 213 293 336 46 234 208 342 274 434 160 292 2 16 233 359 140 220 306 399 6 108 159 380 83 392 208 404 55 201 95 274 145 348 233 257 222 425 28 416 130 344 277 312 233 435 222 245 346 362 10 220 50 252 61 132 54 251 22…
Output: 67

Constraints:

1 <= n <= 2701; 0 <= m <= 5402; 1 <= u,v <= n.

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