Commutable Islands

• Time : $O(BlogA + BlogB)$
• Space : $O(A)$

#include <bits/stdc++.h>

int uf[60606];

int find(int u) {
    return uf[u] == u ? u : uf[u] = find(uf[u]);
}

void uni(int u, int v) {
    int pu = find(u), pv = find(v);
    uf[pu] = uf[pv] = min(pu,pv);
}

int Solution::solve(int A, vector<vector<int> > &B) {
    iota(begin(uf), end(uf),0);
    int res = 0;
    sort(begin(B), end(B), [](auto& A, auto& B) {return A[2] < B[2];});
    for(auto b : B) {
        int u = b[0], v = b[1], c = b[2];
        if(find(u) == find(v)) continue;
        res += c;
        uni(u,v);
    }
    return res;
}