Kruskal (MST): Really Special Subtree

• Time : O(eloge + vlogv)

• Space : O(v + e)

• union find solution

c++

int uf[3030];
int find(int u) {
    return u == uf[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 kruskals(int n, vector<int> f, vector<int> t, vector<int> w) {
    priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>>> pq;
    int m = f.size();
    for(int i = 1; i <= n; i++ )uf[i] = i;
    for(int i = 0; i < m; i++) {
        pq.push({w[i], f[i], t[i]});
    }
    int res = 0;
    while(!pq.empty()) {
        auto [w, u, v] = pq.top(); pq.pop();
        if(find(u) == find(v)) continue;
        res += w;
        uni(u,v);
    }
    
    return res;
}

• Time : O(eloge)

• Space : O(v + e)

• kruskal algorithm solution

c++

int kruskals(int n, vector<int> f, vector<int> t, vector<int> w) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int, int>>> pq;
    vector<pair<int, int>> adj[n + 1];
    bool inc[n + 1];
    memset(inc, false, sizeof inc);
    int m = f.size();
    for(int i = 0; i < m; i++) {
        adj[f[i]].push_back({w[i], t[i]});
        adj[t[i]].push_back({w[i], f[i]});
    }
    inc[1] = true;
    for(auto& [w, v] : adj[1]) {
        pq.push({w, v});
    }
    int res = 0;
    while(!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if(inc[u]) continue;
        inc[u] = true;
        for(auto& [w, v] : adj[u]) {
            if(!inc[v]) pq.push({w, v});
        }
        res += w;
    }

    return res;
}