一条单向的铁路线上，依次有编号为 1, 2, …, n的 n个火车站。每个火车站都有一个级别，最低为 1 级。现有若干趟车次在这条线路上行驶，
每一趟都满足如下要求：如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站x 的都必须停靠。
（注意：起始站和终点站自然也算作事先已知需要停靠的站点）
例如，下表是5趟车次的运行情况。其中，前4 趟车次均满足要求，而第 5 趟车次由于停靠了 3 号火车站（2 级）却未停靠途经的 6 号火车站（亦为 2 级）而不满足要求。
现有 m 趟车次的运行情况（全部满足要求），试推算这n 个火车站至少分为几个不同的级别。
思路:每条路线上,那些没有在路线标注的点的编号一定是要小于原本路线上的点的编号的,这样列车才能正常运行，
所以我们对那些空白点向路径上的点连边,进行拓扑分层,找出最大的dep就是结果
code:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1005; const int inf = 0x3f3f3f3f; const ll mod = 100000000; struct edge { int f, t, nxt; }e[1000005]; int hd[maxn], tot; void add(int f, int t) { e[++tot] = { f,t,hd[f] }; hd[f] = tot; } bool is[maxn], vis[maxn][maxn]; int a[maxn], du[maxn], dep[maxn]; int n, m; int tuopo() { queue<int>q; int ans = 0; for (int i = 1; i <= n; i++) { if (du[i] == 0) { q.push(i); dep[i] = 1; ans = max(ans, dep[i]); } } while (!q.empty()) { int u = q.front(); q.pop(); for (int i = hd[u]; i; i = e[i].nxt) { int v = e[i].t; du[v]--; dep[v] = max(dep[v], dep[u] + 1);//dep取路径上最大 ans = max(ans, dep[v]);//找最大值 if (!du[v])q.push(v); } } return ans; } int main() { //freopen("test.txt", "r", stdin); scanf("%d%d", &n, &m); while (m--) { int k; scanf("%d", &k); memset(is, 0, sizeof(is)); for (int i = 1; i <= k; i++) { scanf("%d", a+i); is[a[i]] = 1; } for (int i = a[1]; i <= a[k]; i++) {//遍历路径上的所有站点 if (!is[i]) {//找到未停靠的点 for (int j = 1; j <= k; j++) { //对其余需要停靠的点连边,表示停靠点编号一定大于未停靠点,这样汽车才能正常运行 if (!vis[i][a[j]]) {//连过边就不再连了 add(i, a[j]); du[a[j]]++; vis[i][a[j]] = 1; } } } } } int ans = tuopo(); cout << ans << endl; return 0; }