题解 | 小红的图上加边

import java.util.*;

public class Main {

    static ArrayList<Integer>[] adj;
    static int[] a;
    static int m,n;
    static boolean[] visited;
    
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);

        n = input.nextInt();
        m = input.nextInt();

        a = new int[n+1];
        visited = new boolean[n+1];
        //初始化邻接表
        adj = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            adj[i] = new ArrayList<>();
        }

        for(int i=1;i<=n;i++){
            a[i] = input.nextInt();
        }

        for(int i=0;i<m;i++){
            int u = input.nextInt();
            int v = input.nextInt();
            adj[u].add(v);
            adj[v].add(u);
        }

        long ans = searchMinCost();

        System.out.println(ans);
    }

    public static long searchMinCost(){
        int cur=0;
        long min = Integer.MAX_VALUE,sum =0;
        for(int i=1;i<=n;i++){
            if(!visited[i]){
                cur = bfs(i);
                sum += (long)cur;
                min = Math.min(min,(long)cur);
            }
        }
        return sum - min;

    }

    public static int bfs(int core){
        Queue<Integer> q = new ArrayDeque<>();

        int maxNum;

        q.offer(core);
        visited[core] = true;
        maxNum = a[core];
        while(q.size() != 0){
            int cur = q.poll();
            for(int x:adj[cur]){
                if(!visited[x]){
                    q.offer(x);
                    visited[x] = true;
                    maxNum = Math.max(a[x],maxNum);
                }
            }
        }

        return maxNum;
    }
}

BFS求每个连通分量的最大值，加和所有最大值，再减去最小的那个就是答案