题目描述

一条单向的铁路线上，依次有编号为 $1, 2, …, n$ 的 $n$ 个火车站。

每个火车站都有一个级别，最低为 $1$ 级。

现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 $x$，则始发站、终点站之间所有级别大于等于火车站 $x$ 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点） 

例如，下表是 $5$ 趟车次的运行情况。

其中，前 $4$ 趟车次均满足要求，而第 $5$ 趟车次由于停靠了 $3$ 号火车站（$2$ 级）却未停靠途经的 $6$ 号火车站（亦为 $2$ 级）而不满足要求。

现有 $m$ 趟车次的运行情况（全部满足要求），试推算这 $n$ 个火车站至少分为几个不同的级别。

输入格式

第一行包含 $2$ 个正整数 $n, m$，用一个空格隔开。

第 $i + 1$ 行（$1 ≤ i ≤ m$）中，首先是一个正整数 $s_i$（$2 ≤ s_i ≤ n$），表示第 $i$ 趟车次有 $s_i$ 个停靠站；接下来有 $s_i$ 个正整数，表示所有停靠站的编号，从小到大排列。

每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

输出格式

输出只有一行，包含一个正整数，即 $n$ 个火车站最少划分的级别数。

数据范围

$1 \le n,m \le 1000$

输入样例：

Copy

9 3 
4 1 3 5 6 
3 3 5 6 
3 1 5 9 

输出样例：

Copy

3

解题思路

整体思路

首先看题（逃
看完题目后我们可以发现：答案就是拓扑排序的最高层数！

1. 建图

想到这里，我们就先建一个图，$a$ -> $b$ 表示 $a$ 的级别小于 $b$
但是怎么建呢？
由于每趟车只能停靠级别大于始发站的站台，所以对于如果一趟车没有停靠某个站就说明那个站比所有停靠过的站都小，要一次向当前所有停靠过的站台连边

2.拓扑排序

建完图后，就可以开始拓扑排序啦！
我们设$dist[i]$为i号节点所在的层
初始时，每一个节点都在第一层
然后每次把一个新的入度为0的节点入队时，把那个节点所在的层加一。

3.答案

由于答案就是拓扑排序的最高层数，所以把dist数组求一个最大值即可

代码

#include <bits/stdc++.h>
using namespace std;
int deg[1005], tmp[1005], dist[1005], is[1005], n, m;
int to[1005][1005];
queue<int> q;
void toposort() {        // 拓扑排序
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0) q.push(i), dist[i] = 1;
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        for (int j = 1; j <= n; j++) {
            if (to[i][j]) {
                if (deg[j] > 0) deg[j]--;
                if (deg[j] == 0) q.push(j), dist[j] = dist[i] + 1;
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {    // 建图
        int s;
        cin >> s;
        memset(is, 0, sizeof is);
        for (int j = 1; j <= s; j++) cin >> tmp[j], is[tmp[j]] = true;
        for (int j = tmp[1]; j <= tmp[s]; j++) {
            if (!is[j]) {
                for (int k = 1; k <= s; k++) {
                    if (to[j][tmp[k]] == 0) {    // 连边
                        to[j][tmp[k]] = 1;
                        deg[tmp[k]]++;
                    }
                }
            }
        }
    }
    toposort();
    int ans = 1;
    for (int i = 1; i <= n; i++) ans = max(ans, dist[i]);    // 取最大值
    cout << ans;
    return 0;
}

关于我memset(is, 0, sizeof is)写成了memset(is, 0, sizeof tmp)这件事，卡了我将近 30 min……