MST: 1584. Min Cost to Connect All Points

Minimum spanning tree

This is a weekly contest problem of Sep12, 2020.

1584. Min Cost to Connect All Points

For the minimum spanning tree, we can either use the Prim algorithm or the Kruskal algorithm.

Kruskal algorithm (TLE)

passed all 72 cases but got TLE.

typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
class UF {
    public:
    vi p, setSize;
    UF(int n) {
        p.assign(n, 0); for (int i = 0; i < n; ++i) p[i] = i;
        setSize.assign(n, 1);
    }
    int getSetSize(int i) {return setSize[i];}
    int findSet(int i) {return p[i] == i ? i : (p[i] = findSet(p[i]));}
    void unionSet(int i, int j) {
        if (findSet(i) == findSet(j)) return;
        int x = findSet(i), y = findSet(j);
        p[x] = y;
        setSize[y] += setSize[x];
        return;
    }
};
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& p) {
        const int n = p.size();
        if (n==1) return 0;
        UF uf(n);
        vector<iii> EL;
        int cost = 0;
        for (int i = 0; i < n; ++i){
            vector<iii> this_EL;
            for (int j = i +1 ; j<n; ++j){
                cost = abs(p[i][0] - p[j][0])+abs(p[i][1] - p[j][1]);
                EL.emplace_back(cost, i, j);    
            }
        }  
        int num_taken = 0;
        int ret = 0;
        sort(EL.begin(), EL.end());
        for (auto &[w, u, v]: EL){
            if (uf.findSet(u) == uf.findSet(v)) continue;
            uf.unionSet(u, v);
            ret += w;
            num_taken++;
            if (num_taken == n-1) break;
        }
        return ret;
    }
};

Kruskal algorithm 2 (TLE again)

slightly improved it a little bit still got TLE.

typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
class UF {
    public:
    vi p, setSize;
    UF(int n) {
        p.assign(n, 0); for (int i = 0; i < n; ++i) p[i] = i;
        setSize.assign(n, 1);
    }
    int getSetSize(int i) {return setSize[i];}
    int findSet(int i) {return p[i] == i ? i : (p[i] = findSet(p[i]));}
    void unionSet(int i, int j) {
        if (findSet(i) == findSet(j)) return;
        int x = findSet(i), y = findSet(j);
        p[x] = y;
        setSize[y] += setSize[x];
        return;
    }
};
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& p) {
        const int n = p.size();
        if (n==1) return 0;
        UF uf(n);
        vector<vector<iii>> EL(n);
        int cost = 0;
        for (int i = 0; i < n; ++i){
            vector<iii> this_EL;
            for (int j = i +1 ; j<n; ++j){
                cost = abs(p[i][0] - p[j][0])+abs(p[i][1] - p[j][1]);
                this_EL.emplace_back(-cost, i, j);    
            }
            sort(this_EL.begin(), this_EL.end());
            EL[i] = this_EL;
        }  
        int num_taken = 0;
        int ret = 0;
        priority_queue<iiii> min_hq;
        for (int i = 0; i < n -1; ++i) {
            auto [w, u, v] = EL[i].back();
            min_hq.emplace(w, u, v, i);
            EL[i].pop_back();
        }
        while(true) {
            auto [w, u, v, i] = min_hq.top();min_hq.pop();
            if (uf.findSet(u) == uf.findSet(v)) {
                if (!EL[i].empty()){
                auto [w, u, v] = EL[i].back();
                min_hq.emplace(w, u, v, i);
                EL[i].pop_back();
            }
                continue;
            }
            uf.unionSet(u, v);
            ret -= w;
            num_taken++;
            if (num_taken == n-1) break;
            if (!EL[i].empty()){
                auto [w, u, v] = EL[i].back();
                min_hq.emplace(w, u, v, i);
                EL[i].pop_back();
            }
        }
        return ret;
    }
};

Kruskal algorithm 3(AC)

Change tuple to pair, got AC.

class UF {
    public:
    vi p, setSize;
    UF(int n) {
        p.assign(n, 0); for (int i = 0; i < n; ++i) p[i] = i;
        setSize.assign(n, 1);
    }
    int getSetSize(int i) {return setSize[i];}
    int findSet(int i) {return p[i] == i ? i : (p[i] = findSet(p[i]));}
    void unionSet(int i, int j) {
        if (findSet(i) == findSet(j)) return;
        int x = findSet(i), y = findSet(j);
        p[x] = y;
        setSize[y] += setSize[x];
        return;
    }
};
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& p) {
        const int n = p.size();
        if (n==1) return 0;
        UF uf(n);
        vector<pair<int, pair<int, int>>> EL;
        int cost = 0;
        for (int i = 0; i < n; ++i){
            vector<iii> this_EL;
            for (int j = i +1 ; j<n; ++j){
                cost = abs(p[i][0] - p[j][0])+abs(p[i][1] - p[j][1]);
                EL.emplace_back(cost, make_pair(i, j));    
            }
        }  
        int num_taken = 0;
        int ret = 0;
        sort(EL.begin(), EL.end());
        for (auto &[w, par]: EL){
            auto [u, v] = par;
            if (uf.findSet(u) == uf.findSet(v)) continue;
            uf.unionSet(u, v);
            ret += w;
            num_taken++;
            if (num_taken == n-1) break;
        }
        return ret;
    }
};

Take away

usually, the tuple and pair should not have that much difference. For this one, it seems that the pair is faster. So using pair in the future for this kind of problem.