虽然这是道普及组的题，但解决的过程还真是挺曲折的。。。QwQ
本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P1983
也捣鼓了很久的图论了（其实并没有多久），打算把这道题作为一个分界点，转去学一会DP。没想到，看完题目，我的第一反应并不是图论知识。
最初的思路是这样，对于每个站点，先设置级别为1，然后对于读入的每趟列车，因为读入的车站级别一定比没读入的高，就检查每个车站，不合格就修改。结果只有20分，仔细一想确实不对。对于每趟列车，读入车站的级别应当保证一直比未读入的高，然而这种只考虑本趟列车的做法，显然可能会与之前的产生冲突。
然后就开始考虑图论怎么做，比较容易想到的是将大小关系用边来表示，然后跑拓扑排序（其实一开始就想到了），令人不安的是建图过程，复杂度极高！没办法，还是硬着头皮写吧。但是只有60分，提示是运行时错误，那肯定数组开小了。最多有1000个点，又因为是有向图且不会出现两个点之间有两条边的情况，所以边数不会超过1000*(1000-1)/2。把数组稍稍调大一点，咦，怎么成了70分。
看题解。。。哦！原来在读入边的过程中，因为是用邻接链表存边，每条边可能被读入多次！所以需要加一个标志数组，或者是使用邻接矩阵存边。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 5 using namespace std; 6 7 inline int get_num() { 8 int num = 0; 9 char c = getchar(); 10 while (c < '0' || c > '9') c = getchar(); 11 while (c >= '0' && c <= '9') 12 num = num * 10 + c - '0', c = getchar(); 13 return num; 14 } 15 16 const int maxn = 1005; 17 18 int graph[maxn][maxn], ind[maxn], stop[maxn], vis[maxn], level[maxn]; 19 20 queue<int> q; 21 22 int main() { 23 int n = get_num(), m = get_num(), ans = 0; 24 for (int i = 1; i <= m; ++i) { 25 int s = 0, t = 0, cnt = get_num(); 26 memset(stop, 0, sizeof(stop)); 27 memset(vis, 0, sizeof(vis)); 28 for (int j = 1; j <= cnt; ++j) { 29 if (j == 1) vis[s = stop[j] = get_num()] = 1; 30 else if (j == cnt) vis[t = stop[j] = get_num()] = 1; 31 else vis[stop[j] = get_num()] = 1; 32 } 33 for (int j = 1; j <= cnt; ++j) { 34 for (int k = s; k <= t; ++k) 35 if (!vis[k] && !graph[k][stop[j]]) 36 graph[k][stop[j]] = 1, ++ind[stop[j]]; 37 } 38 } 39 for (int i = 1; i <= n; ++i) 40 if (!ind[i]) { 41 level[i] = 1; 42 q.push(i); 43 } 44 while (!q.empty()) { 45 int u = q.front(); 46 q.pop(); 47 for (int v = 1; v <= n; ++v) 48 if (graph[u][v]) { 49 if (level[v] < level[u] + 1) 50 level[v] = level[u] + 1; 51 if (!(--ind[v])) q.push(v); 52 } 53 if (ans < level[u]) ans = level[u]; 54 } 55 printf("%d", ans); 56 return 0; 57 }