题解 | 小红的图上加边

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> mx(n);
    for (int i = 0; i < n; ++i) cin >> mx[i];
    int cc = n;
    vector<int> fa(n);
    iota(fa.begin(), fa.end(), 0);
    auto find = [&](auto&& self, int x) -> int{
        if (fa[x] != x){
            int f = self(self, fa[x]);
            mx[x] = max(mx[x], mx[f]);
            fa[x] = f;
        }
        return fa[x];
    };
    auto merge = [&](int x, int y) -> bool{
        int a = find(find, x), b = find(find, y);
        if (a == b) return false;
        cc--;
        fa[a] = b;
        mx[b] = max(mx[a], mx[b]);
        return true;
    };
    for (int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        merge(u, v);
    }
    vector<int> ans;
    vector<char> vis(n, 'f');
    for (int i = 0; i < n; ++i){
        int f = find(find, i);
        if (vis[f] == 'f'){
            ans.push_back(mx[f]);
            vis[f] = 't';
        }
    }
    sort(ans.begin(), ans.end());
    ll s = 0;
    for (int i = 1; i < ans.size(); ++i)    s += ans[i];
    cout << s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}