题解 | 小红的图上加边

#include <iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
const int N=1e5+10;
int a[N],f[N];
long long sum=0;
set<int>b;
vector<int>c[N],d;
bool cmp(int x,int y)
{
    return x>y;
}
int find(int x)
{
    if(f[x] != x)
        f[x] = find(f[x]);  
    return f[x];
}
int main() 
{

   int n,m;
   cin>>n>>m;
   for(int i=1;i<=n;i++)
   {
    cin>>a[i];
    f[i]=i;
   }
   for(int i=1;i<=m;i++)
   {
    int x,y;
    cin>>x>>y;
     int fx = find(x);
    int fy = find(y);
    if(fx != fy) f[fx] = fy;

   }
   for(int i=1;i<=n;i++)
   {
    if(b.find(find(i))==b.end())
    {
        b.insert(f[i]);
    }
    c[f[i]].push_back(a[i]);
   }
   for(int it:b)
   {
    sort(c[it].begin(),c[it].end(),cmp);
    d.push_back(c[it][0]);
   }
   sort(d.begin(),d.end());
   for(int i=1;i<d.size();i++)
   {
    sum+=d[i];
   }
   cout<<sum;
}
// 64 位输出请用 printf("%lld")