CT56828

Varun's tunnels Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the mining town of Ironvein with crates of tunnels, and Varun the chronicler must account for every last one. 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 <= 1740; 0 <= m <= 3480; 1 <= u,v <= n.

Example 1:

Input: 135 2001 11 64 18 72 79 106 52 74 55 99 42 70 25 53 24 76 14 26 62 90 8 65 54 88 14 51 44 76 10 70 88 109 10 121 35 49 7 15 58 108 83 86 108 132 87 106 32 71 93 132 1 119 69 82 28 108 73 117 3 102 37 51 29 97 7 77 60 91 40 75 24 95 52 59 23 32 42 49 76 112 101 109 40 118 111 126 46 88 24 26 107 115 34 84 21 103 94 117 25 90 33 110 58 77 80 129 32 109 116 126 84 103 28 126 22 129 35 134 46 109 13 85 49 53 48 63 77 113 9 23 46 85 44 120 38 96 109 112 2 84 81 122 19 34 43 85 45 115 99 129 96 125 32 98 68 96 81 118 10 66 61 84 29 32 113 115 14 27 17 70 59 125 27 105 35 126 91 118 26 120 32 94 42 74 1 124 123 132 60 134 104 118 15 33 42 119 37 99 10 84 23 106 2 39 2 21 77 110 19 117 93 108 37 48 18 121 17 126 11 115 22 105 53 124 73 87 8 121 10 130 17 104 15 28 64 129 6 122 74 124 73 82 3 73 25…
Output: 1

Example 2:

Input: 191 149 26 114 25 140 71 81 147 187 5 18 73 175 23 52 24 146 41 65 30 43 111 151 119 190 94 143 80 88 186 188 153 155 157 178 56 164 17 143 93 94 96 114 21 61 27 101 40 150 20 176 127 187 86 159 51 172 72 130 34 50 1 53 163 172 45 173 15 20 13 80 42 184 50 140 40 153 159 191 20 118 92 101 115 130 122 146 3 156 125 156 38 134 35 50 116 163 38 115 119 172 52 137 90 164 105 140 44 183 154 189 69 168 38 55 111 152 3 96 50 138 20 84 36 179 2 137 22 58 4 78 53 122 30 130 51 119 26 162 49 159 134 135 127 167 22 122 102 144 66 153 17 93 10 52 126 163 134 173 56 129 4 162 161 180 35 171 139 141 95 163 5 86 123 182 103 135 112 140 16 61 12 152 54 97 81 139 17 23 20 79 45 130 60 86 7 47 57 92 4 152 164 188 58 122 46 56 159 180 76 80 24 46 9 58 24 177 114 158 40 92 20 67 116 125 22 42 82 98 4 126 105 …
Output: 51

Example 3:

Input: 1086 3442 533 744 80 342 32 285 422 695 133 628 459 588 208 646 42 585 577 862 223 1056 731 1044 182 842 924 981 738 784 116 423 37 541 300 707 442 1060 144 556 77 362 155 674 155 649 237 1044 251 841 91 1065 6 578 631 1027 873 1053 602 625 160 429 819 887 301 352 127 324 304 922 791 1041 484 831 556 890 262 439 196 662 181 539 523 848 554 711 384 698 124 329 779 1084 262 546 24 222 34 977 133 818 845 1077 236 929 140 232 217 744 184 566 603 1056 68 777 104 658 366 459 522 649 789 1079 578 957 548 639 46 204 83 223 185 918 129 132 50 808 31 41 223 1085 501 618 333 962 553 665 742 954 148 953 571 864 3 1012 201 388 68 751 5 548 902 991 27 809 255 958 277 622 321 391 249 291 563 931 583 773 187 466 203 707 91 721 896 1029 154 634 377 868 385 414 371 531 507 736 234 271 75 414 191 686 342 816…
Output: 6

Constraints:

1 <= n <= 1740; 0 <= m <= 3480; 1 <= u,v <= n.

Loading...
Test Cases:No test cases
No test cases available.
Varun's tunnels Reckoning - MEDIUM Coding Problem | CodeTikki