Java O(m + n)遍历解法 题解 | 探索宇宙中的星系联盟

首先遍历输入，使用map记录星系和文明等级的对应关系，初始时将所有星系看作一个单独的星系团

然后遍历道路输入，对于每一个输入，存在两种情况

1. 如果道路两侧已经在同一个星系团中，跳过
2. 如果道路两侧不在同一个星系团中，则将这两个星系团合并

最后遍历所有星系团，找出其中最大的星系团和其中文明等级最高的星系

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int starNumber = in.nextInt();
        HashMap<String , Integer> starLevel = new HashMap<>();
        List<ArrayList<String>> starList = new ArrayList<>();
        for(int i = 0; i < starNumber;i ++){
            String starName = in.next();
            int level = in.nextInt();
            starLevel.put(starName,level);
            ArrayList<String> list = new ArrayList<>();
            list.add(starName);
		  	//初始时所有星系单独放置
            starList.add(list); 
        }
        int roadNum = in.nextInt();
        for(int i = 0; i < roadNum;i++){
            String starName1 = in.next();
            String starName2 = in.next();
            int size = starList.size();
            for(int j = 0;j < size;j++){
                if(starList.get(j).contains(starName1)){
                    //如果两个星系本就在一起，则跳过
                    if(starList.get(j).contains(starName2))break;
                    else for(int k = 0;k < size;k++){
                        if(starList.get(k).contains(starName2)){
                            //此时两个星系j和k是联通的，将他们放入同一个list中
                            starList.get(j).addAll(starList.get(k));
                            starList.remove(starList.get(k));
                            size --;
                            break;
                        }
                    }
                    break;
                }
            }
        }
        int maxTotal = 0;
        String maxString = "";
        for(int i = 0;i < starList.size();i ++){
            int curTotal = 0;
            String curMaxString = "";
            int curMaxLevel = 0;
            for(String str:starList.get(i)){
                int curLevel = starLevel.get(str);
                curTotal+= curLevel;
                if(curLevel > curMaxLevel){
                    curMaxLevel = curLevel;
                    curMaxString = str;
                }
            }
            if(curTotal > maxTotal){
                maxTotal = curTotal;
                maxString = curMaxString;
            }
        }
        System.out.print(maxString + " " + maxTotal);

    }
}