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

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
//import javax.swing.text.html.Map;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        // 读取星系总数
        int n = sc.nextInt();
        sc.nextLine();
        // 存储星系名称到文明等级的映射
        Map<String,Integer> map=new HashMap<>();
        // 存储所有星系名称
        List<String> allGalaxies=new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String[] arr = sc.nextLine().split(" ");
            String name = arr[0];
            int level = Integer.parseInt(arr[1]);
            map.put(name,level);
            allGalaxies.add(name);
        }

        // 读取星际航道总数
        int m = sc.nextInt();
        sc.nextLine();
        // 构建邻接表表示星系间的连接关系
        Map<String,List<String>> relationship=new HashMap<>();
        for (String galaxy:allGalaxies) {
            relationship.put(galaxy,new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            String[] arrStr = sc.nextLine().split(" ");
            String a = arrStr[0];
            String b = arrStr[1];
            relationship.get(a).add(b);
            relationship.get(b).add(a);
        }

        // 找出所有连通分量（星系联盟）
        Set<String> visited=new HashSet<>();
        List<List<String>> alliances=new ArrayList<>();
        for (String galaxy:allGalaxies) {
            if (!visited.contains(galaxy)){
                List<String> alliance=new ArrayList<>();
                dfs(galaxy,visited,relationship,alliance);
                alliances.add(alliance);
            }
        }

        // 计算每个联盟的总实力，并找出最强联盟
        int max=0;

        List<String> stragenestAlliance=null;
        for (List<String> alliance:alliances) {
            int total=0;
            for (String galaxy:alliance) {
                total+=map.get(galaxy);
            }
            if (total>max){
                max=total;
                stragenestAlliance=alliance;
            }
        }

        int highestLevel=0;
        String highestLevelGalaxy="";
        // 找出最强联盟中文明等级最高的星系
        for (String galaxy:stragenestAlliance) {
            int level = map.get(galaxy);
            if (level>highestLevel){
                highestLevel=level;
                highestLevelGalaxy=galaxy;
            }
        }
        System.out.println(highestLevelGalaxy+" "+max);
    }
    
    public static void dfs(String current,Set<String> visited,Map<String,List<String>> relationship,        List<String> alliance){
        visited.add(current);
        alliance.add(current);
        for (String neighbor:relationship.get(current)) {
            if (!visited.contains(neighbor))
            dfs(neighbor,visited,relationship,alliance);
        }
    }
}