#include<bits/stdc++.h>
using namespace std;
// 定义常量 N 作为最大极点数
const int N = 30010;
// n 表示图的极点数量，m 表示图的边数量
int n, m;
// in 数组用于记载每个极点的入度，入度即指向该极点的边的数量
int in[N];
// q 数组作为队列利用，用于拓扑排序过程中存储入度为 0 的极点
int q[N];
// h 是队列的头指针，初始化为 0；t 是队列的尾指针，初始化为 -1
int h = 0, t = -1;
// f 数组是一个 bitset 数组，f 表示从极点 i 出发能够到达的全部极点的聚集// bitset 是一种高效存储二进制位的数据结构，这里用它可以方便地进行位运算
bitset<N> f[N];
// e 是一个无序映射，用于存储图的毗邻表// e 存储的是从极点 u 出发的全部边指向的极点
unordered_map<int, vector<int>> e;
// 拓扑排序函数，用于对有向图进行拓扑排序
bool toposort() {
// 遍历全部极点，将入度为 0 的极点加入队列
for (int i = 1; i <= n; i++) {
if (!in) {
// 入度为 0 的极点入队，尾指针后移
q[++t] = i;
}
}
// 当队列不为空时，持续进行处理惩罚
while (h <= t) {
// 取出队头元素
int u = q[h++];
// 遍历从极点 u 出发的全部边指向的极点
for (int v : e) {
// 将极点 v 的入度减 1，表示移除从 u 到 v 的边
--in[v];
// 如果极点 v 的入度变为 0，将其加入队列
if (!in[v]) {
q[++t] = v;
}
}
}
// 这里原代码直接返回 1，存在问题，正确应该判断是否拓扑排序乐成
// 若拓扑排序乐成，队列中应该存储了全部极点，即 t == n - 1
return t == n - 1;
}
int main() {
// 读取图的极点数量 n 和边的数量 m
scanf("%d%d", &n, &m);
// 循环读取每条边的信息
for (int i = 0; i < m; i++) {
int u, v;
// 读取边的起点 u 和终点 v
scanf("%d%d", &u, &v);
// 将终点 v 添加到起点 u 的毗邻表中
e.push_back(v);
// 终点 v 的入度加 1
in[v]++;
}
// 按照拓扑排序结果的逆序遍历极点
for (int i = n - 1; i >= 0; i--) {
// 取出当前处理惩罚的极点
int u = q;
// 极点 u 能到达自身，将 f 的第 u 位设为 1
f = 1;
// 遍历从极点 u 出发的全部边指向的极点
for (int v : e) {
// 通过位运算将 f[v] 能到达的极点合并到 f 中
f |= f[v];
}
}
// 遍历全部极点，输出每个极点能到达的极点数量
for (int i = 1; i <= n; i++) {
// count() 方法返回 bitset 中 1 的个数，即能到达的极点数量
cout << f.count() << endl;
}
return 0;
}
车站分级：
分析
这道题可以通过建立有向图并进行拓扑排序来求解火车站最少的级别数，以下是具体思绪：
建立有向图思绪
极点含义：将每个火车站看作图中的一个极点，编号为 1 到 n ，对应图中的 n 个极点。
边的构建：对于每一趟车次，设其停靠站为 si1,si2,⋯,sisi（按编号从小到大分列）。对于这趟车次的任意两个停靠站 sij 和 sik（j<k），在图中添加有向边 (sij,sik)。这是因为根据题目条件，如果一趟车次停靠了火车站 x，则始发站、终点站之间全部级别大于等于火车站 x 的都必须停靠，添加边表示了这种级别上的 “约束” 关系。更普通地理解，就是停靠靠前的车站可以 “指向” 停靠靠后的车站，意味着靠前车站的级别小于等于靠后车站的级别。
边的隐含意义：有向边 (u,v) 表示火车站 u 的级别小于等于火车站 v 的级别。通过这样构建有向图，就将车次运行情况转化为了图中极点之间的关系。
拓扑排序思绪
