無向グラフの最小全域木

vector<vector<pair<int,int»> の状態のグラフを入れる

最小全域木のコストが返ってくる

非連結の場合は-1が返ってくる

long long cost(vector<vector<pair<long long,long long>>>& v){
    long long n = v.size();
    long long ans = 0;
    dsu d(n);
    priority_queue<pair<long long,pair<long long,long long>>,vector<pair<long long,pair<long long,long long>>>,greater<pair<long long,pair<long long,long long>>>> q;
    rep(i,n)for(pair<long long,long long> p : v[i]){
        if(p.first > i){
            q.push({p.second,{i,p.first}});
        }
    }
    while(q.size()!=0){
        long long w = q.top().first;
        long long x = q.top().second.first;
        long long y = q.top().second.second;
        q.pop();
        if(!d.same(x,y)){
            ans += w;
            d.merge(x,y);
        }
    }
    if(d.size(0)!=n)return -1;
    return ans;
}

最小全域木の内容が欲しい場合

vector<pair<long long,long long>>  cost(vector<vector<pair<long long,long long>>>& v){
    long long n = v.size();
    vector<pair<long long,long long>> ans;
    dsu d(n);
    priority_queue<pair<long long,pair<long long,long long>>,vector<pair<long long,pair<long long,long long>>>,greater<pair<long long,pair<long long,long long>>>> q;
    rep(i,n)for(pair<long long,long long> p : v[i]){
        if(p.first > i){
            q.push({p.second,{i,p.first}});
        }
    }
    while(q.size()!=0){
        long long w = q.top().first;
        long long x = q.top().second.first;
        long long y = q.top().second.second;
        q.pop();
        if(!d.same(x,y)){
            d.merge(x,y);
            ans.push_back({x,y});
        }
    }
    if(d.size(0)!=n)return1;
    return ans;
}