题解 | 小红的图上加边-并查集-java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    static class Dsu{
        int[]parent;
        long[]maxVal;
        public Dsu(int n,long[]a){
            parent=new int[n+1];
            maxVal=new long[n+1];
            for (int i = 1; i <=n; i++) {
                parent[i]=i;
                maxVal[i]=a[i-1];
            } 
        }
        public int find(int x){
            if(parent[x]==x) return x;
            return parent[x]=find(parent[x]);
        }
        public void union(int x,int y){
            int rootx=find(x);
            int rooty=find(y);
            if(rootx!=rooty){
                parent[rootx]=rooty;
                maxVal[rooty]=Math.max(maxVal[rootx], maxVal[rooty]);
            }
        }

    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        long[]a=new long[n];
        for (int i = 0; i < n; i++) {
            a[i]=sc.nextLong();
        }   
        Dsu dsu=new Dsu(n, a);
        for (int i = 0; i < m; i++) {
            int u=sc.nextInt();
            int v=sc.nextInt();
            dsu.union(u, v);
        }
        List<Long>list=new ArrayList<>();
        for (int i = 1; i <=n; i++) {
            if(dsu.parent[i]==i){
                list.add(dsu.maxVal[i]);
            }
        }
        if(list.size()<=1){
            System.out.println(0);
        }else{
            Collections.sort(list);
            long total=0;
            for (int i = 1; i <list.size(); i++) {
                total+=list.get(i);
            }
            System.out.println(total);
        }
        sc.close();
    }
}