CT31024

Farhan's Painted bridges

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Every season at the boar woods of Tuskmore, someone must optimize the storeroom layout. This year the task falls to Farhan, armed only with the bridges register. 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 <= 1637; 0 <= m <= 3274; 1 <= u,v <= n.

Example 1:

Input: 147 1439 27 39 81 94 100 146 15 55 27 127 79 89 37 57 40 92 24 115 3 4 7 63 27 57 28 47 23 125 56 106 6 101 102 124 22 31 94 132 28 130 56 140 18 59 59 146 96 99 52 131 2 72 37 62 68 137 121 139 1 145 23 96 102 129 91 146 113 144 44 121 132 135 75 107 82 121 25 130 62 86 76 121 90 125 26 82 34 115 17 85 19 101 6 10 57 101 47 63 88 107 20 137 102 137 139 142 103 127 7 145 123 137 38 117 66 141 18 119 10 63 71 75 15 18 69 71 36 121 50 77 73 111 108 140 81 86 113 119 33 63 47 71 48 95 88 140 76 124 65 134 31 72 38 103 78 81 19 99 114 147 109 112 75 116 37 107 23 70 38 115 101 147 69 132 86 96 22 121 64 70 43 45 78 90 127 129 31 105 34 146 92 100 8 46 32 65 98 121 80 103 5 113 114 132 17 48 36 71 34 53 26 145 42 127 1 39 19 103 39 139 9 66 59 107 53 101 48 134 57 136 10 107 30 142 4 5 9 44 56 …
Output: 1

Example 2:

Input: 989 2613 744 960 818 826 261 591 3 585 22 539 161 686 600 672 130 370 34 766 409 837 24 580 115 479 238 962 150 295 1 626 162 504 157 597 195 336 260 850 568 893 449 745 348 547 469 559 220 249 339 564 643 901 278 767 279 368 239 716 251 827 792 851 631 721 261 530 246 669 552 768 44 424 261 387 323 463 301 497 794 964 338 431 122 907 257 417 167 370 78 908 167 741 21 698 35 459 142 939 745 762 743 888 24 207 102 733 533 805 559 816 716 815 88 556 630 943 337 445 26 275 243 264 317 747 212 349 170 261 316 781 365 510 510 792 19 774 358 420 185 665 172 745 211 339 53 678 26 898 213 791 414 764 812 972 33 611 340 948 146 688 302 346 367 504 424 793 415 440 591 686 554 821 406 806 111 457 521 553 173 742 240 778 145 629 569 893 10 866 93 701 675 896 510 924 215 804 61 938 71 875 5 64 177 442 …
Output: 9

Example 3:

Input: 151 3230 83 118 23 46 121 129 38 116 97 106 79 95 113 149 85 136 16 151 40 131 39 102 5 109 46 86 61 141 120 132 18 101 50 100 68 141 59 64 43 51 5 10 55 77 29 109 102 130 90 112 82 146 11 53 7 87 50 123 84 92 59 94 39 143 70 97 55 75 85 116 34 71 89 139 1 99 56 146 14 151 17 49 14 103 35 114 75 121 90 124 91 105 62 89 34 134 83 131 24 99 65 71 49 117 23 34 83 112 79 114 9 102 121 140 32 118 67 121 38 117 136 137 32 41 47 80 30 44 29 82 5 37 27 44 111 116 65 124 81 151 76 128 35 137 90 107 18 66 5 110 2 124 72 106 10 61 31 91 8 61 66 77 95 127 12 22 53 96 37 73 131 151 34 48 22 38 37 58 49 79 121 135 43 89 132 133 3 148 124 136 5 141 109 117 24 82 17 32 39 112 105 134 36 83 80 137 38 49 28 140 126 137 28 78 33 130 94 137 11 72 11 45 61 107 43 135 89 140 36 131 4 142 21 37 96 135 10 20 111 …
Output: 1

Constraints:

1 <= n <= 1637; 0 <= m <= 3274; 1 <= u,v <= n.

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