问题描述
题解
考虑建立有向边\((a,b)\)，代表\(a\)比\(b\)低级。
于是枚举每一辆车次经过的车站\(x \in [l,r]\)，如果不是车辆停靠的车站，则从\(x\)向每个停靠了的车站连边。
拓扑排序，建立分层图，搞出最大的层数即可。
\(\mathrm{Code}\)
#include<bits/stdc++.h>
using namespace std;
template <typename Tp>
void read(Tp &x){
x=0;char ch=1;int fh;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-'){
fh=-1;ch=getchar();
}
else fh=1;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
x*=fh;
}
const int maxn=1007;
const int maxm=1000007;
int k,a[maxn],ina[maxn];
bool exist[maxn][maxn];
int n,m;
int Head[maxn],Next[maxm],to[maxm],tot=1;
int rd[maxn];
void add(int x,int y){
to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;
}
int dep[maxn],ans=1;
void toposort(){
queue<int>q;
for(int i=1;i<=n;i++){
if(!rd[i]){
q.push(i);dep[i]=1;
}
}
while(!q.empty()){
int x=q.front();q.pop();
for(int i=Head[x];i;i=Next[i]){
int y=to[i];--rd[y];
if(!rd[y]){
q.push(y);dep[y]=dep[x]+1;
ans=max(dep[y],ans);
}
}
}
}
int main(){
read(n);read(m);
for(int i=1;i<=m;i++){
read(k);memset(ina,0,sizeof(ina));
for(int j=1;j<=k;j++){
read(a[j]);ina[a[j]]=1;
}
for(int j=a[1];j<=a[k];j++){
if(ina[j]) continue;
for(int p=1;p<=k;p++){
if(!exist[j][a[p]]){
++rd[a[p]];add(j,a[p]);
exist[j][a[p]]=1;
}
}
}
}
toposort();
printf("%d\n",ans);
return 0;
}