题解 | 探索宇宙中的星系联盟

import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] nm = new String[n];
        int[] weight = new int[n];
        Map<String,Integer> ids = new HashMap<>(n);
        for(int i=0;i<n;i++){
            String str = br.readLine();
            nm[i] = str.split(" ")[0];
            weight[i] = Integer.parseInt(str.split(" ")[1]);
            ids.put(nm[i], i);
        }
        int m = Integer.parseInt(br.readLine());
        List<Integer>[] adj = new ArrayList[n];
        for(int i=0;i<n;i++){adj[i] = new ArrayList<>();}
        for(int i=0;i<m;i++){
            String str = br.readLine();
            int idA = ids.get(str.split(" ")[0]);
            int idB = ids.get(str.split(" ")[1]);
            adj[idA].add(idB);
            adj[idB].add(idA);
        }

        boolean[] vis = new boolean[n];
        int bestSum = Integer.MIN_VALUE;
        String bestName = "";
        for(int i=0;i<n;i++){
            if(vis[i]){continue;}
            int maxId = i;
            int sumWeights= 0;
            Deque<Integer> q = new ArrayDeque<>();
            q.add(i);
            vis[i]=true;
            while(!q.isEmpty()){
                int id = q.poll();
                sumWeights+=weight[id];
                if(weight[id]>weight[maxId]){
                    maxId=id;
                }
                for(int idx:adj[id]){
                    if(!vis[idx]){
                    vis[idx]=true;
                    q.add(idx);
                    }
                }
            }
            if(sumWeights>bestSum){
                bestSum=sumWeights;
                bestName=nm[maxId];
            }
        }
        System.out.print(bestName+" "+bestSum);
    }
}