Commutable Islands

struct subset {
    int parent;
    int rnk;
};

int find(struct subset subsets[], int i){
    if(subsets[i].parent == i) return i;
    subsets[i].parent = find(subsets, subsets[i].parent);
    return i;
}

int Union(struct subset subsets[], int a, int b){
    a = find(subsets, a);
    b = find(subsets, b);
    if( a != b ){
        if(subsets[a].rnk > subsets[b].rnk){
            subsets[b].parent = a;
            subsets[a].rnk += subsets[b].rnk;
        }else{
            subsets[a].parent = b;
            subsets[b].rnk += subsets[a].rnk;
        }
        return 1;
    }
    return 0;
}

int Solution::solve(int A, vector<vector<int> > &B) {
    for(int i=0; i<B.size(); i++){
        reverse(B[i].begin(), B[i].end());
    }
    sort(B.begin(), B.end());
    struct subset subsets[A+1];
    for(int i=0; i<=A; i++){
        subsets[i].parent = i;
        subsets[i].rnk = 1;
    }
    int sum=0, cnt=0;
    for(auto v:B){
        if(find(subsets, v[1]) != find(subsets, v[2])){
            Union(subsets, v[1], v[2]);
            sum += v[0];
            cnt++;
        }
        if(cnt == A-1){
            return sum;
        }
    }
    return sum;
}

I was trying Commutable Islands but I am not able to pass all the test cases. Can someone suggest where I am going wrong

Problem Link: https://www.interviewbit.com/old/problems/commutable-islands/

This is the test case which I am getting wrong

78
656 3 7 65 610 74 53 927 68 67 263 67 56 277 17 34 275 66 42 822 24 73 984 39 19 324 76 45 820 12 78 488 35 29 177 25 52 682 47 42 192 4 24 783 7 44 255 75 64 73 13 60 979 5 65 131 71 5 443 33 39 966 17 58 9 48 15 102 30 55 807 23 14 961 26 74 1000 75 9 433 50 18 660 32 73 320 38 56 17 43 11 292 1 19 919 21 52 172 77 26 91 27 22 666 32 44 575 25 13 490 64 31 752 18 41 794 36 51 801 51 63 187 36 9 959 2 8 855 10 43 596 33 70 660 59 46 56 23 57 161 49 31 54 76 5 223 68 28 123 10 28 26 27 66 909 20 11 649 59 58 329 45 59 186 53 40 606 54 12 370 69 61 865 57 72 572 37 48 601 29 60 872 63 47 77 15 40 295 16 45 330 34 3 652 54 37 482 6 37 533 30 41 146 62 50 514 8 57 492 22 70 543 78 2 581 35 61 750 49 69 71 14 55 135 21 4 610 77 3 666 38 62 743 2 1 188 3 1 38 4 1 281 5 1 833 6 1 530 7 1 241 8 1 584 9 1 248 10 1 191 11 1 575 12 1 231 13 1 649 14 1 823 15 1 784 16 1 468 17 1 39 18 1 762 20 1 416 21 1 880 22 1 551 23 1 585 24 1 944 25 1 992 26 1 621 27 1 36 28 1 915 29 1 965 30 1 870 31 1 470 32 1 866 33 1 604 34 1 756 35 1 143 36 1 761 37 1 183 38 1 701 39 1 681 40 1 215 41 1 235 42 1 204 43 1 844 44 1 826 45 1 456 46 1 815 47 1 451 48 1 929 49 1 404 50 1 399 51 1 5 52 1 56 53 1 928 54 1 731 55 1 60 56 1 63 57 1 745 58 1 581 59 1 241 60 1 275 61 1 240 62 1 563 63 1 830 64 1 692 65 1 459 66 1 15 67 1 482 68 1 725 69 1 34 70 1 208 71 1 569 72 1 776 73 1 938 74 1 935 75 1 810 76 1 471 77 1 606 78 1 955 3 2 375 4 2 252 5 2 121 6 2 821 7 2 776 9 2 650 10 2 429 11 2 317 12 2 584 13 2 409 14 2 319 15 2 891 16 2 447 17 2 638 18 2 104 19 2 814 20 2 358 21 2 840 22 2 69 23 2 225 24 2 766 25 2 933 26 2 208 27 2 425 28 2 401 29 2 731 30 2 750 31 2 448 32 2 615 33 2 679 34 2 335 35 2 669 36 2 227 37 2 417 38 2 249 39 2 794 40 2 308 41 2 190 42 2 429 43 2 901 44 2 725 45 2 837 46 2 833 47 2 799 48 2 44 49 2 523 50 2 212 51 2 448 52 2 246 53 2 623 54 2 740 55 2 601 56 2 314 57 2 854 58 2 619 59 2 720 60 2 634 61 2 808 62 2 534 63 2 944 64 2 189 65 2 225 66 2 157 67 2 654 68 2 512 69 2 817 70 2 974 71 2 293 72 2 248 73 2 668 74 2 979 75 2 971 76 2 113 77 2 547 4 3 575 5 3 554 6 3 610 7 3 546 8 3 436 9 3 688 10 3 431 11 3 56 12 3 504 13 3 263 14 3 814 15 3 370 16 3 755 17 3 670 18 3 202 19 3 895 20 3 850 21 3 486 22 3 756 23 3 541 24 3 440 25 3 341 26 3 468 27 3 395 28 3 464 29 3 310 30 3 612 31 3 221 32 3 492 33 3 424 35 3 862 36 3 996 37 3 393 38 3 187 39 3 105 40 3 123 41 3 224 42 3 542 43 3 808 44 3 435 45 3 87 46 3 875 47 3 274 48 3 799 49 3 526 50 3 41 51 3 299 52 3 105 53 3 123 54 3 865 55 3 810 56 3 748 57 3 966 58 3 506 59 3 977 60 3 887 61 3 341 62 3 710 63 3 289 64 3 392 65 3 489 66 3 18 67 3 531 68 3 439 69 3 256 70 3 18 71 3 407 72 3 431 73 3 689 74 3 434 75 3 425 76 3 384 78 3 875 5 4 974 6 4 311 7 4 432 8 4 750 9 4 635 10 4 180 11 4 581 12 4 832 13 4 116 14 4 761 15 4 540 16 4 137 17 4 998 18 4 471 19 4 478 20 4 287 22 4 916 23 4 589 25 4 285 26 4 219 27 4 707 28 4 880 29 4 124 30 4 579 31 4 903 32 4 310 33 4 948 34 4 86 35 4 365 36 4 394 37 4 112 38 4 651 39 4 311 40 4 644 41 4 82 42 4 794 43 4 811 44 4 846 45 4 339 46 4 737 47 4 596 48 4 79 49 4 359 50 4 480 51 4 167 52 4 996 53 4 78 54 4 565 55 4 368 56 4 282 57 4 941 58 4 873 59 4 395 60 4 942 61 4 483 62 4 226 63 4 795 64 4 933 65 4 540 66 4 583 67 4 814 68 4 724 69 4 658 70 4 599 71 4 558 72 4 825 73 4 351 74 4 922 75 4 106 76 4 191 77 4 483 78 4 590 6 5 491 7 5 423 8 5 380 9 5 339 10 5 551 11 5 162 12 5 633 13 5 240 14 5 42 15 5 303 16 5 167 17 5 36 18 5 952 19 5 739 20 5 916 21 5 501 22 5 916 23 5 916 24 5 607 25 5 61 26 5 413 27 5 654 28 5 318 29 5 119 30 5 563 31 5 414 32 5 557 33 5 895 34 5 910 35 5 529 36 5 446 37 5 15 38 5 648 39 5 230 40 5 772 41 5 915 42 5 270 43 5 424 44 5 911 45 5 918 46 5 106 47 5 565 48 5 491 49 5 914 50 5 964 51 5 977 52 5 1000 53 5 837 54 5 996 55 5 204 56 5 243 57 5 990 58 5 506 59 5 88 60 5 964 61 5 300 62 5 287 63 5 836 64 5 839 66 5 535 67 5 697 68 5 219 69 5 515 70 5 301 72 5 395 73 5 942 74 5 149 75 5 375 77 5 962 78 5 462 7 6 686 8 6 49 9 6 841 10 6 27 11 6 417 12 6 581 13 6 606 14 6 8 15 6 430 16 6 665 17 6 379 18 6 620 19 6 690 20 6 212 21 6 918 22 6 162 23 6 789 24 6 605 25 6 489 26 6 74 27 6 626 28 6 220 29 6 370 30 6 294 31 6 994 32 6 583 33 6 980 34 6 910 35 6 697 36 6 687 38 6 773 39 6 476 40 6 360 41 6 248 42 6 918 43 6 473 44 6 201 45 6 780 46 6 902 47 6 806 48 6 95 49 6 937 50 6 127 51 6 652 52 6 643 53 6 142 54 6 119 55 6 140 56 6 352 57 6 74 58 6 25 59 6 832 60 6 624 61 6 677 62 6 778 63 6 432 64 6 484 65 6 317 66 6 884 67 6 950 68 6 384 69 6 763 70 6 422 71 6 619 72 6 332 73 6 667 74 6 201 75 6 767 76 6 604 77 6 352 78 6 189 8 7 461 9 7 129 10 7 885 11 7 746 12 7 764 13 7 319 14 7 525 15 7 824 16 7 95 17 7 45 18 7 84 19 7 511 20 7 782 21 7 199 22 7 123 23 7 655 24 7 107 25 7 415 26 7 336 27 7 122 28 7 878 29 7 504 30 7 924 31 7 405 32 7 706 33 7 18 34 7 715 35 7 75 36 7 949 37 7 601 38 7 223 39 7 497 40 7 956 41 7 174 42 7 78 43 7 483 45 7 620 46 7 956 47 7 207 48 7 54 49 7 58 50 7 868 51 7 857 52 7 428 53 7 309 54 7 138 55 7 413 56 7 531 57 7 686 58 7 349 59 7 487 60 7 342 61 7 631 62 7 275 63 7 848 64 7 586 66 7 153 67 7 298 68 7 615 69 7 251 70 7 436 71 7 672 72 7 99 73 7 388 74 7 323 75 7 101 76 7 195 77 7 466 78 7 173 9 8 796 10 8 502 11 8 2 12 8 398 13 8 654 14 8 19 15 8 447 16 8 755 17 8 646 18 8 235 19 8 581 20 8 130 21 8 133 22 8 10 23 8 632 24 8 640 25 8 504 26 8 913 27 8 198 28 8 384 29 8 805 30 8 567 31 8 465 32 8 395 33 8 674 34 8 963 35 8 62 36 8 491 37 8 950 38 8 668 39 8 360 40 8 22 41 8 438 42 8 697 43 8 261 44 8 713 45 8 145 46 8 625 47 8 408 48 8 451 49 8 613 50 8 789 51 8 414 52 8 765 53 8 440 54 8 969 55 8 897 56 8 841 58 8 311 59 8 527 60 8 936 61 8 424 62 8 394 63 8 59 64 8 941 65 8 178 66 8 678 67 8 376 68 8 965 69 8 58 70 8 858 71 8 409 72 8 980 73 8 136 74 8 114 75 8 817 76 8 606 77 8 77 78 8 767 10 9 76 11 9 983 12 9 410 13 9 645 14 9 363

What’s the input format?
It looks like the input you provided is not valid input.

This is the test case provided by the site.

??

The first argument contains an integer, A, representing the number of islands.
The second argument contains an 2-d integer matrix, B, of size M x 3:
    => Island B[i][0] and B[i][1] are connected using a bridge of cost B[i][2].

The 2nd line denotes the array like B[0][0], B[0][1], B[1][0], B[1][1]…so on

1 <= A, M <= 6e4
1 <= B[i][0], B[i][1] <= A
1 <= B[i][2] <= 1e3

So, if the following is a valid input,

78
656 3 7 65 610 74 53 ...

Then 1 \le 656 \le 78 becomes true. :slightly_smiling_face:

1 Like

Okay so I think there’s some problem with the site only

Anyways, my score was 196/200 for that problem. Here’s my code (you may find it useful).

Python Code
class Solution:
    def __init__(self):
        parent = None
        self.weight = None
    
    def initialise(self, nax):
        self.parent = [i for i in range(nax + 10)]
        self.weight = [1 for i in range(nax + 10)]
        
    def get(self, a: int) -> int:
        while self.parent[a] != a:
            self.parent[a] = self.parent[self.parent[a]]
            a = self.parent[a]
        return a
        
    def union(self, a, b):
        parent_a = self.get(a)
        parent_b = self.get(b)
        if self.weight[parent_a] <= self.weight[parent_b]:
            self.weight[parent_b] += self.weight[parent_a]
            self.parent[parent_a] = self.parent[parent_b]
        else:
            self.weight[parent_a] += self.weight[parent_b]
            self.parent[parent_b] = self.parent[parent_a]
    # @param A : integer
    # @param B : list of list of integers
    # @return an integer
    def solve(self, A, tuples):
        self.initialise(A)
        tuples.sort(key = lambda x: x[2])
        included = 0
        ind = 0
        ans = 0
        while included < A - 1 and ind < len(tuples):
            if self.get(tuples[ind][0]) == self.get(tuples[ind][1]):
                ind += 1
                continue
            ans += tuples[ind][2]
            self.union(tuples[ind][0], tuples[ind][1])
            ind += 1
            included += 1
        return ans
1 Like