Untitled

 avatar
unknown
plain_text
4 years ago
1.1 kB
3
Indexable
#include <bits/stdc++.h>
#define pll pair<ll, ll>
#define ll long long
#define pb push_back
#define in(n) scanf("%lld", &n)
#define deb(n) cout << #n << n << endl
#define fo(i, a, b) for (ll i = a; i < b; i++)
#define fon(i, a, b) for(ll i =a; i<=b; i++)
#define vpll vector<pll>
#define F first
#define S second
using namespace std;
const ll mx = 1e5;
vector<ll> g[mx + 1];
bool vis[mx + 1];
void dfs(ll i) {
    if (vis[i]) return;
    vis[i] = 1;
    for (auto v : g[i])
        dfs(v);
}

void solve(){
    vpll qu;
    ll n, q, u, v, a;
    in(n);
    in(q);
    qu.push_back({0, 0});
    fon(i, 1 ,n){
        in(a);
        qu.push_back({a, i});
    }
    sort(qu.begin(), qu.end());
    fo(i, 0, q){
        in(u);
        in(v);
        g[u].pb(v);
        g[v].pb(u);
    }
    ll cnt = 0;
    fon(i, 1, n){
        if(!vis[qu[i].S]){
            cnt+=qu[i].F;
            dfs(qu[i].S);
            //cout<<qu[i].S<<" "<<qu[i].F<<" "<<cnt<<endl;
        }
    }
    printf("%lld", cnt);
}

int main(void) {
    int t =1;
    //in(t);
    while(t--){
        solve();
    }
}










Editor is loading...