CT49807

Brevin's signals Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the copper works of Verdigris. Brevin spreads the signals records across the table and picks up a sharp pencil. Task: n isolated nodes are joined by m edges (some may be redundant). Print the minimum number of additional edges needed to make the graph connected. Input format: First line: n and m. Next m lines: u v. Output format: Print the number of extra edges needed. Constraints: 1 <= n <= 4000; 0 <= m <= 4000.

Example 1:

Input: 4000 2728 151 3756 707 1629 296 2624 404 767 584 2023 1379 3657 2430 2465 420 771 942 2415 1327 1350 555 2902 1610 2339 2879 3152 2604 3607 487 3849 1717 2956 2978 3948 325 3836 898 1813 1875 3654 404 2994 520 1762 1000 3563 1729 3099 2431 3416 1407 3533 681 2301 164 2613 2759 3448 583 3614 39 3641 913 2028 1434 3473 2319 2412 2452 2936 3259 3735 1144 1366 785 1047 805 1102 3226 3396 709 3474 957 1921 1150 1593 1104 3403 1748 3587 1165 2805 2738 3669 112 992 2520 3325 3013 3280 1589 2796 1034 3374 605 2866 366 3042 1721 2184 3071 3734 1472 2922 3021 3885 2715 3318 2417 3487 1326 1838 1433 1472 573 2815 1090 2429 2105 3133 739 3498 2649 3540 2643 3424 3431 3632 62 2927 1742 3089 520 1733 2342 3641 186 2849 2794 3389 1529 2645 9 2807 3012 3055 2432 2675 755 3350 38 1110 1321 1981 2548 3602 1…
Output: 1332

Example 2:

Input: 2 0
Output: 1

Example 3:

Input: 100 3664 11 79 56 92 42 59 52 93 59 65 81 87 23 27 22 47 32 90 11 22 37 46 7 56 47 61 40 74 2 43 31 68 61 78 8 16 62 88 18 58 49 96 53 56 32 60 47 55 66 84 19 43 39 70 16 45 16 19 24 65 44 59 41 62 53 65 20 87 71 80 39 82 1 19 91 100 22 26 35 88 59 66 62 89 39 63 17 47 20 49 30 95 94 96 37 91 17 91 8 19 7 57 34 75 37 83 35 86 61 90 17 18 3 53 15 48 10 38 47 83 35 42 72 92 4 22 5 66 79 93 13 21 25 59 22 91 27 66 33 88 13 95 33 71 40 49 73 97 4 38 7 17 40 72 9 30 35 82 2 19 35 96 20 71 59 84 20 93 32 64 4 95 31 83 41 45 69 74 43 92 46 80 54 81 24 91 10 26 4 44 40 51 51 86 31 65 36 43 21 68 27 31 36 63 8 38 63 68 7 99 75 89 54 60 3 32 61 98 19 84 52 95 96 99 2 65 3 68 37 41 1 97 81 89 12 67 41 82 4 45 50 68 87 99 7 97 24 46 78 89 64 87 62 63 25 38 74 79 32 84 84 94 26 48 73 91 22 27 5 81 80 9…
Output: 0

Constraints:

1 <= n <= 4000; 0 <= m <= 4000.

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