CT34530

Galen's roads Separate Camps

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Legend says the vault under the shipyard of Keelwind opens only for a perfect tally of roads. Galen means to find out. 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 <= 1541; 0 <= m <= 3082; 1 <= u,v <= n.

Example 1:

Input: 199 1688 6 93 50 161 64 165 35 153 11 118 23 94 29 161 134 178 12 145 118 133 2 18 115 170 107 164 96 134 120 184 126 162 25 26 12 183 125 170 41 68 20 32 41 52 37 91 54 150 26 129 90 178 25 100 13 48 22 157 84 91 45 105 13 165 111 159 27 66 12 65 9 37 20 81 153 193 56 147 13 192 117 173 112 129 111 183 43 178 78 84 130 198 82 102 20 148 67 181 134 174 25 120 55 77 7 82 9 114 67 162 17 169 54 114 78 129 4 5 103 173 89 141 93 116 49 189 193 194 27 197 188 194 71 80 58 162 112 146 14 50 80 139 93 97 167 195 7 79 22 198 168 199 185 188 80 111 43 114 111 124 164 183 110 196 54 182 70 162 41 58 60 191 8 110 82 131 56 97 24 158 109 181 76 102 36 107 157 168 88 109 26 87 31 183 1 45 114 167 115 131 77 92 49 101 47 65 74 166 8 118 9 59 35 139 14 152 116 144 33 68 60 187 95 172 109 177 102 196 100 …
Output: 1

Example 2:

Input: 1276 2683 302 428 888 944 1083 1209 515 796 564 578 12 1244 403 1224 891 1212 693 1132 340 714 733 863 182 874 1047 1131 715 991 155 630 523 933 193 481 109 891 151 839 524 865 865 1072 1004 1250 290 617 803 1078 700 1267 534 876 162 186 803 1191 267 329 134 148 1220 1242 116 1195 797 1151 624 1189 717 1038 80 345 617 713 105 1271 711 1260 633 1193 464 719 453 991 99 1182 733 1202 90 987 574 957 44 1082 334 1005 714 1163 444 503 155 374 1120 1136 888 1019 578 885 201 1201 584 781 97 849 383 397 178 889 552 767 314 721 73 966 94 932 202 706 156 320 514 938 660 1164 665 1061 592 1235 294 891 443 478 265 1067 322 525 509 835 230 1252 184 443 240 641 538 1082 391 1092 1063 1249 439 1170 240 619 1097 1116 268 695 944 1269 100 721 19 95 975 1136 555 843 350 520 792 1032 330 498 818 858 449 744 4…
Output: 22

Example 3:

Input: 3 1 2 3
Output: 2

Constraints:

1 <= n <= 1541; 0 <= m <= 3082; 1 <= u,v <= n.

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