Advertisement
Guest User

Untitled

a guest
Aug 20th, 2018
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define forr(i, a, b) for(int i=(int)(a);i<(int)(b);i++)
  4. #define forn(i,n) forr(i,0,n)
  5. #define dforn(i,n) for(int i=(int)(n-1);i>=0;i--)
  6. #define forall(it, v) for(auto it=v.begin();it!=v.end();it++)
  7. #define pb push_back
  8. typedef long long ll;
  9. const int MAXN=200050;
  10.  
  11. ll c[MAXN];
  12. int n,m;
  13. vector<int> G[MAXN];
  14. bool used[MAXN];
  15.  
  16. ll dfs(int v, int p){
  17.     used[v]=true;
  18.     ll ans=c[v];
  19.     forn(i,G[v].size()){
  20.         int w=G[v][i];
  21.         if(w==p) continue;
  22.         if(used[w]) continue;
  23.         ans=min(ans,dfs(w,v));
  24.     }
  25.     return ans;
  26. }
  27.  
  28. int main() {
  29.     //~ freopen("F.in", "r", stdin);
  30.     while(scanf("%d%d",&n,&m)>=1){
  31.         memset(used,false,sizeof(used));
  32.         forn(i,MAXN)G[i].clear();
  33.         forn(i,n){
  34.             scanf("%lld",&c[i]);
  35.         }
  36.         forn(i,m){
  37.             int a,b;
  38.             scanf("%d%d",&a,&b);
  39.             --a;--b;
  40.             G[a].pb(b);
  41.             G[b].pb(a);
  42.         }
  43.         ll ans=0;
  44.         forn(i,n){
  45.             if(!used[i]){
  46.                 ans+=dfs(i,-1);
  47.             }
  48.         }
  49.         printf("%lld\n",ans);
  50.     }
  51.     return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement