差分约束裸题。
计算当前线路中最小的级别（比较始发站和终点站）。
整条线路中所有大于这个级别的都必须停靠
所有未停靠的站点的级别一定小于这个级别

也就是说所有未停靠的即为级别低，记为A
所有停靠的站点级别一定比A的高，记作B
得到公式$B ≥ A + 1$
根据很明显是一道差分约束问题。
根据差分约束的概念，我们从所有的A向所有的B连一条权值为1的有向边。

然后根据差分约束的套路，我们还要设一个界限才能求出最大值。

因为所有车站级别都是正值，所以$A≥1$，也就是从0向所有的A中的点连一条权值为1 的有向边。我们常常用直接给dist数组赋值为1代替。

但是由于实际数据范围较大

最坏情况下是有1000趟火车，每趟有1000个点，每趟上限有500个点停站，则有(1000 - 500)个点不停站，不停站的点都向停站的点连有向边，则总共有 $500 * 500 * 1000 = 2.5 * 10^8$，差分约束的spfa有可能超时。

由于本题中的所有点的权值都是大于0，并且一定满足要求$=>$所有车站都等级森严$=>$不存在环$=>$可以拓扑排序得到拓扑图使用递推求解差分约束问题。

因此整体的思路为：

• 拓扑排序得拓扑图
• “至少”$=>$要求的是最小值$=>$所有条件的下界中取最大值$=>$最长路，因此我们，根据拓扑序跑最长路递推即可。
• 答案为满足所有约束条件的解中最大值既是题目要求的最高的级别

一个建图的优化：

如果直接暴力建图就会建$O(nm)$条边，也就是$2*10^8$个点，时间和空间都有可能超时。

我们可以在中间建一个虚拟节点，左边向虚拟点连0，虚拟点向右边连1等价于左边向右边连1

这样只会建$O(n + m)$条边

注意的是本题一共m条线路,每条线路一个虚拟源点,所以一共会有n + m 个点。

当年出题人并没有卡这一点，不然要卡死一大批有志青年

如下图所示：

优化前：

然后就是代码了

别忘了一共有n + m 个点

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>

using namespace std;

const int N = 2007, M = 5000007;

int n, m;
int ver[M], nex[M], edge[M], head[N], tot;
int din[N];
int vis[N];
int q[N];
int dist[N];

void add(int x, int y, int z){
    ver[tot] = y;
    edge[tot] = z;
    nex[tot] = head[x];
    head[x] = tot ++ ;
    din[y] ++ ;
}

void toposort(){
    int hh = 0, tt = -1;
    for(int i = 1;i <= n + m;++i){//一共n + m个点,要遍历所有的点
        if(!din[i]){
            q[++ tt] = i;
            if(tt == N)tt = 0;
        }
    }

    while(hh <= tt){

        int x = q[hh ++ ];
        if(hh == N)hh = 0;

        for(int i = head[x];~i;i = nex[i]){
            int y = ver[i];
            if(-- din[y] == 0){
                q[++ tt] = y;
                if(tt == N)tt = 0;
            }
        }
    }
}

int main(){
    scanf("%d%d", &n,&m);
    memset(head,-1,sizeof head);

    for(int i = 1;i <= m;++i){
        memset(vis,0,sizeof vis);
        int t,stop;
        scanf("%d",&t);
        int start = n, end = 1;
        while(t -- ){
            scanf("%d",&stop);//输入的是编号
            start = min(start, stop);
            end = max(end, stop);
            vis[stop] = true;//代表该站要停靠.
        }
        int source = n + i;//n + 1
        for(int j = start;j <= end;++j){//该线路上的所有经过的站点的编号一定在始发站和终点站之间
            if(vis[j])//要停靠,说明是右部点
                add(source, j, 1);
            else add(j, source, 0);
        }
    }

    toposort();

    for(int i = 1;i <= n;++i)//A ≥ 1
        dist[i] = 1;
    for(int i = 0;i < n + m;++i){//手写的队列是从0开始的
        int x = q[i];
        for(int j = head[x];~j;j = nex[j]){
            int y = ver[j], z = edge[j]; 
            dist[y] = max(dist[y], dist[x] + z);
        }
    }
    int res = 0;
    for(int i = 1;i <= n;++i)//满足所有约束条件的解中最大值既是题目要求的最高的级别
        res = max(res, dist[i]);

    printf("%d\n",res);
    return 0;
}