CT33944

Ranger and the Hidden canals

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Ranger found an old ledger of canals in the mill attic at the peat bogs of Mossgrieve. The margin notes pose a precise question. 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 <= 1215; 0 <= m <= 2430; 1 <= u,v <= n.

Example 1:

Input: 183 111 35 161 83 160 54 76 128 163 68 137 32 176 79 101 24 118 2 74 39 88 83 153 46 102 81 105 91 145 113 125 31 127 62 80 86 135 134 160 97 149 65 147 108 160 58 87 139 158 6 67 124 149 6 109 51 131 38 105 128 176 45 148 24 53 2 28 64 103 21 132 2 151 105 182 140 143 8 97 98 155 4 137 25 74 17 40 78 126 60 101 90 124 87 163 90 160 108 179 100 164 33 38 51 147 4 127 15 165 103 122 78 123 73 172 71 132 127 140 47 51 38 108 68 162 40 75 87 161 34 168 108 146 22 55 76 106 108 169 30 137 56 140 157 178 15 155 68 150 137 183 22 183 32 160 28 54 26 89 45 177 56 98 51 168 53 114 83 100 45 142 20 49 173 180 9 143 111 173 6 164 17 19 36 159 81 146 24 59 122 154 29 149 47 119 11 112 51 156 40 58 85 88 37 85 24 175 8 37 50 153 1 93 82 166 59 62 50 156 102 179 61 172
Output: 73

Example 2:

Input: 26 322 8 22 19 23 9 21 3 19 16 17 14 17 12 15 2 15 22 23 25 26 3 10 2 10 7 14 8 19 6 24 6 15 5 22 15 16 18 19 8 20 15 24 4 17 6 25 20 22 21 22 12 23 2 19 17 26 3 18 1 15 5 25 4 6 12 26 5 8 2 23 15 26 18 26 3 26 8 16 3 7 1 18 7 25 22 25 10 19 6 7 2 3 17 23 2 9 4 11 20 26 10 15 11 26 18 24 20 24 6 14 6 9 3 12 3 9 3 22 1 25 18 23 17 24 8 14 17 21 11 12 5 6 12 21 6 16 1 19 6 18 10 22 7 19 7 23 4 19 19 21 4 26 13 19 1 22 14 23 7 18 8 10 1 16 16 19 7 8 13 20 1 3 17 22 16 24 18 25 13 22 19 24 15 21 6 23 6 19 2 5 15 20 14 24 12 16 13 26 24 26 3 14 9 23 10 11 11 13 12 19 13 23 5 20 22 26 3 4 11 25 2 21 3 20 9 20 1 2 10 24 1 7 17 18 12 17 12 18 2 13 14 25 14 19 3 21 5 17 2 14 3 24 9 19 14 26 15 25 15 22 4 8 2 20 4 10 2 16 7 21 4 13 4 22 16 25 5 26 11 18 1 26 10 16 5 7 1 13 2 4 1 20 4 16 5 12 10 25 1…
Output: 1

Example 3:

Input: 1142 2140 135 1078 570 866 10 1001 857 1046 436 1031 11 1065 269 955 304 314 56 955 258 479 471 1056 416 672 803 1097 108 665 192 400 156 200 124 517 798 1111 298 933 133 287 821 926 543 828 517 976 786 1138 667 1105 561 846 283 302 114 1125 735 1028 353 483 879 899 760 912 831 850 5 891 579 750 889 937 107 566 296 615 103 407 191 1116 105 936 640 717 202 607 314 514 359 1107 68 728 185 1134 296 886 650 886 589 948 698 734 69 969 675 708 478 886 596 914 219 841 114 572 450 1125 414 962 292 833 211 391 409 958 566 1036 696 1073 99 1037 160 429 235 887 280 727 335 1033 433 729 439 1009 196 308 986 1069 437 1044 767 981 1004 1126 393 672 418 599 476 881 59 982 227 935 337 1109 640 889 167 517 280 383 315 724 99 812 412 845 862 869 95 1129 986 1114 293 736 465 798 511 526 243 346 312 515 481 6…
Output: 27

Constraints:

1 <= n <= 1215; 0 <= m <= 2430; 1 <= u,v <= n.

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