Nowcoder9983G.糖果（并查集）

链接：https://ac.nowcoder.com/acm/contest/9983/G
来源：牛客网

在一个幼儿园里面有nmathit nn个小朋友，分别编号1,2,...,n ext 1,2,...,n1,2,...,n。在这些小朋友中有一些小朋友互为朋友关系，总共有mmathit mm对朋友。
作为幼儿园老师，你想买一些糖果分给小朋友，你知道第imathit ii个小朋友想要至少aia_{i}ai​个糖果，否则他就会不开心。
同时，如果一个小朋友得到的糖果数小于他某个朋友得到的糖果数，他也会不开心。
请问你最少买多少糖果才能保证每个小朋友都不会不开心呢？

一道并查集模板题，估计是给没学过并查集的人熟悉一下。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
int n,m;
int a[maxn];
int father[maxn];
int num[maxn];
int findfather (int x) {
    int a=x;while (x!=father[x]) x=father[x];
    while (a!=father[a]) {
        int z=a;a=father[a];father[z]=x;
    }
    return x;
}
void Union (int x,int y) {
    x=findfather(x);
    y=findfather(y);
    if (x==y) return;
    if (a[x]<=a[y]) {
        father[x]=y;
        num[y]+=num[x];
        num[x]=0;
    }
    else {
        father[y]=x;
        num[x]+=num[y];
        num[y]=0;
    }
}
int main () {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",a+i);
    for (int i=1;i<=n;i++) father[i]=i,num[i]=1;
    for (int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        Union(x,y);
    }
    long long ans=0;
    for (int i=1;i<=n;i++) {
        if (findfather(i)==i) ans+=1ll*num[i]*a[i];
    }
    printf("%lld
",ans);
}