代码描述

拓扑排序，AcWing能过，pta最后两个样例点超时
优化不动了（千手观音强如怪物 拼尽全力无法战胜

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static FastReader in = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    public static void main(String[] args) {
        int N = in.nextInt();
        Map<String, Integer> map = new HashMap<>();
        String[][] srr = new String[N][];
        int globalIndex = 0;

        for (int i = 0; i < N; i++) {
            srr[i] = in.next().split("\\.");
            for (String str : srr[i]) {
                if (!map.containsKey(str)) map.put(str, globalIndex++);
            }
        }

        int[] inDegree = new int[globalIndex];
        List<Integer>[] largerMembers = new ArrayList[globalIndex];
        for (int i = 0; i < globalIndex; i++) {
            largerMembers[i] = new ArrayList<>();
        }

        String[] toStr = new String[globalIndex];
        for (Entry<String, Integer> entry : map.entrySet()) {
            toStr[entry.getValue()] = entry.getKey();
        }

        for (int i = 0; i < N-1; i++) {
            if (srr[i].length==srr[i+1].length) {
                for (int j = 0; j < srr[i].length; j++) {
                    if (!srr[i][j].equals(srr[i+1][j])) {
                        int i1 = map.get(srr[i][j]), i2 = map.get(srr[i+1][j]);
                        largerMembers[i1].add(i2);
                        inDegree[i2] += 1;
                        break;
                    }
                }
            }
        }

//      System.out.println(Arrays.toString(toStr));

        Comparator<Integer> comparator = (i1, i2)->toStr[i1].compareTo(toStr[i2]);
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(comparator);

        for (int i = 0; i < globalIndex; i++) {
            if (inDegree[i]==0) priorityQueue.add(i); // 添加入读为0的节点
        }

        StringBuilder sb = new StringBuilder();

        while (!priorityQueue.isEmpty()) {
            int nextNode = priorityQueue.poll();
            sb.append(toStr[nextNode]).append(".");
            for (Integer integer: largerMembers[nextNode]) {
                if (--inDegree[integer] == 0) {
                    priorityQueue.add(integer);
                }
            }
        }

        sb.deleteCharAt(sb.length()-1);
        out.print(sb.toString());
        out.flush();
    }
}
class FastReader {
    BufferedReader br;
    StringTokenizer st;
    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    public String next() {
        while (st==null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
    public double nextDouble() {
        return Double.parseDouble(next());
    }
}