写在前面

其实如果没有给出是图论题的话，这题就难在想不想得到拓扑了。

题面

1.定义"要求"：对于任意停靠的车站，存在优先级，需要满足其余大于等于该车站优先级的车站必须停靠的条件。

2.给出满足"要求"的几条线路，求出需要划分的最少优先级数量。

思路

1.首先，我们确定一下每条线路需要处理的车站：从起点到终点这一段路上的所有车站。

2.对于"优先"这个概念，我们可以联系到图论中的父子关系，也就是建立有向边。

3.对于有向边，当我们将优先级小的车站作为父节点、优先级大的作为子节点时，就可以采用拓扑排序的逻辑。在每次push的时候，我们只需存入当前节点的优先级，依次迭代并记录优先级的最大值即可。

4.对于建立有向边，我们可以遍历这条线路上所有非停靠站，将所有车站依次连到各个非停靠车站上即可。

AC(java)代码

import java.util.*;

public class Main{

    private static class Point{ //防止构建泛型数组
        int inDegree;
        List<Integer> edges = new ArrayList<>();
    }

    //实现cpp里面的pair
    private static class Pair<A, B>{
        A A;
        B B;

        public Pair(A a, B b) {
            A = a;
            B = b;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            if (!Objects.equals(A, pair.A)) return false;
            return Objects.equals(B, pair.B);
        }

        @Override
        public int hashCode() {
            int result = A != null ? A.hashCode() : 0;
            result = 31 * result + (B != null ? B.hashCode() : 0);
            return result;
        }
    }

    static int n, ans;
    static Point[] points;
    static boolean[][] edgeVisited;

    static void addEdge(int x, int y){
        if(points[x] == null) points[x] = new Point();
        if(points[y] == null) points[y] = new Point();
        points[x].edges.add(y);
        points[y].inDegree ++;
    }

    static void topSort() { //拓扑排序
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++)
            if (points[i] != null && points[i].inDegree == 0) { //多余的站不用管了
                queue.offer(new Pair<>(i, 1)); //入度为零，优先级最低为1
            }
        while (queue.size() > 0) {
            Pair<Integer, Integer> x = queue.poll();
            for (int y : points[x.A].edges) {
                if (--points[y].inDegree == 0) {
                    queue.offer(new Pair<>(y, x.B + 1)); //当所有能遍历到y的点都经过了，那就可以can can y了(不然会有重复
                    ans = Math.max(ans, x.B + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int m = scanner.nextInt();
        points = new Point[n + 1];
        edgeVisited = new boolean[n + 1][n + 1];
        for(int w=0;w<m;w++){
            int s = scanner.nextInt();
            List<Integer> stations = new ArrayList<>();
            boolean[] isStation = new boolean[n + 1];
            for(int i=0;i<s;i++) {
                int now = scanner.nextInt();
                stations.add(now);
                isStation[now] = true;
            }
            for(int i=stations.get(0); i<=stations.get(s - 1);i++){ //非车站作为车站的爸爸建有向边
                if(isStation[i]) continue;
                for(int j : stations){
                    if(!edgeVisited[i][j]){
                        edgeVisited[i][j] = true;
                        addEdge(i, j);
                    }
                }
            }
        }
        topSort();
        System.out.println(ans);
    }
}

这题也可以用邻接表。

要交题的话还是建议cpp哈，java有点卡时间了。

若有错误，还请大佬们指点。