CT45510

June and the Separate Camps

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

June found an old ledger of tunnels in the dairy attic at the gristmill of Rye Hollow. 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 <= 1546; 0 <= m <= 3092; 1 <= u,v <= n.

Example 1:

Input: 156 2432 10 16 13 19 38 139 1 87 38 128 85 109 13 75 85 141 29 121 45 99 81 133 44 96 11 121 94 155 15 94 47 134 13 47 141 149 22 143 39 55 51 127 35 119 16 104 10 138 8 36 77 116 58 149 24 50 34 72 62 139 48 118 91 116 10 91 70 91 60 93 1 23 16 116 6 124 43 96 14 135 35 154 95 118 27 63 9 134 141 153 110 111 134 135 128 145 88 96 99 122 7 123 69 135 49 84 26 77 3 56 48 127 1 88 25 35 91 122 60 87 29 152 102 147 114 137 111 135 17 33 72 136 25 108 36 103 8 81 73 148 44 50 8 25 13 128 2 93 28 130 58 64 14 156 79 121 133 142 45 76 72 139 51 93 31 132 5 37 54 121 25 146 22 67 58 125 25 77 12 64 60 114 24 34 66 139 53 58 2 50 25 57 46 90 1 52 35 68 24 80 17 34 76 94 7 16 47 154 22 57 52 78 118 119 100 115 81 148 53 79 84 91 24 96 104 128 109 121 4 155 14 77 54 109 17 78 104 153 58 132 60 103 1…
Output: 1

Example 2:

Input: 252 1537 72 165 110 214 92 183 84 135 70 84 8 29 12 74 91 93 71 114 214 241 81 241 198 209 102 113 19 220 205 209 66 220 214 218 118 197 143 180 120 131 86 178 44 81 15 26 6 156 46 81 149 231 135 234 109 137 38 113 56 177 35 76 141 250 227 246 16 17 130 181 202 224 27 60 22 97 145 250 161 250 34 120 119 168 6 33 6 91 30 119 228 252 219 236 80 189 98 100 82 243 40 117 45 139 139 158 30 101 24 65 13 177 83 114 97 248 47 193 52 75 5 67 47 212 219 235 87 195 100 116 30 154 73 76 46 116 61 160 14 113 96 178 107 146 24 29 51 75 22 120 90 144 55 84 100 184 169 245 91 231 92 222 147 241 192 250 25 157 5 36 45 183 136 167 40 45 145 168 5 160 5 171 61 208 41 100 100 229 3 34 82 112 108 251 36 81 142 174 46 138 45 159 85 165 42 90 16 205 81 124 128 234 9 79 125 126 65 167 168 198 16 195 92 234 25 77 …
Output: 1

Example 3:

Input: 276 1494 111 262 94 124 240 247 163 254 60 186 256 266 3 14 46 131 163 271 82 194 102 120 41 129 19 274 7 63 42 170 89 113 90 265 132 154 183 239 244 267 227 240 59 126 79 171 246 274 22 82 6 46 72 170 167 238 144 245 145 270 36 72 230 241 177 182 167 190 188 236 78 244 90 129 136 160 112 246 20 255 93 267 177 254 91 178 96 203 5 263 117 135 115 171 85 143 75 158 32 196 20 204 76 192 14 256 70 176 71 132 249 270 91 206 188 228 6 251 208 220 64 85 57 96 43 115 137 168 19 49 166 174 110 269 132 244 68 170 97 135 143 178 61 218 159 261 82 158 30 180 82 149 9 124 119 207 7 163 73 101 63 214 137 202 23 25 115 134 61 168 7 196 140 241 65 89 17 65 40 128 45 57 205 257 46 89 57 262 122 240 70 236 102 140 15 139 74 186 102 149 163 275 88 93 173 181 97 274 102 245 60 208 158 170 3 117 61 88 46 112 9…
Output: 1

Constraints:

1 <= n <= 1546; 0 <= m <= 3092; 1 <= u,v <= n.

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