首先，有这个题单是因为 NOIP 2020 的第一题考到了拓扑排序，并且似乎题单区并没有这个题单的说（
其次，也写了学习笔记，也当自己的任务计划训练一下吧。
目前是 13 道题，如果再看到值得刷的题目还会新增，欢迎私信。
事实上，拓扑排序就是将一个图变化为一个线性序列的过程。
故，我愿称之为降维打击。
我们依然按照网上一贯的方式引入，假设一中有以下
在每一项前的数字是他们的编号，而在他们后面的数字则是 前置课程，换言之，要想学
先随便选一个试试看吧！看着信息学电竞就觉得很有意思诶，看看：要先学这么多？？那看看前置课程中的修电脑罢……诶，也有前置课程？看看前置课程珂学研究——终于没有前置课程了！可以从这里开始学。那么，没有前置课程 的内容就是我们要先开始学的内容了。
那么，我们可以把所有没有前置课程的内容先学完。这里有一个重要的“删除”操作：如果我学过了
那么学完珂学研究之后，课程变成了这样：
这时候我们发现
诶，
那么就可以学习信息学了！这是最后一个课程；至此，我们学课程的顺序如下：
对于这样的一个可行的顺序，我们称之为“拓扑序”，由于在同时有多个前置为零的课程时，选任何一个都可以（不影响结果），所以拓扑序可能有多种多样的结果，这不影响我们选课（对吧）。
诶，已经都没有前置课程了！那么就都学吧，先学前面的或者后面的都不影响（想一想，为什么），所以一种可行的学课程顺序是这样的：
这样的一个可行的顺序，我们称之为“拓扑序”，由于在同时有多个前置课程时，选任何一个都可以（不影响结果），所以拓扑序可能有多种多样的结果，这不影响我们选课（对吧）。
那么我们可以把这个过程抽象成一个图论的模型：
那么上面的课程就可以抽象成这样（箭头从前置课程指向下一个课程）：
那么我们学完珂研之后就变成了这样：
接下来的过程也显然简单不少（以此类推就行了）。
但是不如设想一个极其简单的场面（纯属虚构）：
那你会发现，当你想学那个常数大的东西时要先学树状数组，想学树状数组又要学线段树……这不是陷入死循环了么？其实，当这个图存在环时是不能进行拓扑排序的（原因如上），所以，能跑拓扑排序的一定是一个无环图，而且还得是一个有向图，那么，综合起来就是：
关键在于，哪些点是 入度为
我们的关键在于维护一个入度为零的集合。
当我们要删除一个节点
这完了么？其实并没有——当你删除这些边时，他们指向的节点入度就减一了，这时，我们要把入度减一后为
那么我们来做一下例题吧。
以下为不改变题意的简化版描述。
有
多测，每组第一行为
要求给出一个合理的排名，输出时队伍号之间有空格，最后一名后面没有空格。
其他说明：排名可能不唯一，故要求输出时编号小的队伍在前；输入数据保证有解。
Sample Input
4 3
1 2
2 3
4 3Sample Output
1 2 4 3抽象化是一个重要的工具。
这时候我们考虑：如果
你说这出题人为了省 SPJ 就麻烦做题人呗
那么我们约定一下变量名字：
那么我们需要循环找到入度为零且编号最小的节点
多测记得清空，不知道为啥要防重边，鉴于细节有点多，还是放一下参考代码供大家对拍啥的。
#include<bits/stdc++.h>
using namespace std;
bool mp[505][505];//存边（是否存在）
int in[505],n,m;//存入度，以及两个变量
queue<int>q;//存拓扑排序后路径
void print(){
//鉴于奇怪的输出要求，决定写个输出函数
printf("%d",q.front()); //输出第一个
q.pop();//出队
while(!q.empty()){
printf(" %d",q.front());//输出
q.pop();//出队
}puts("");//换行
}void topo(){
for(int i=1;i<=n;i++){
int s;//找到编号最小的、入度为 0 的节点
for(int j=1;j<=n;j++){
if(in[j]==0){
//找出前驱数量为零的的点
s=j;
break;
}
}q.push(s);in[s]=-1;//将第一名的前驱数量设为-1
for(int j=1;j<=n;++j){
//将相关（前驱为 s）的点处理
if(mp[s][j]){
in[j]--;//入度减 1
mp[s][j]=0;//删掉这条边
}
}
}print();//输出
}int main(){
while(cin>>n>>m){
memset(in,0,sizeof(in));//初始化
memset(mp,0,sizeof(mp));
for(int i=0;i<m;i++){
int x,y;cin>>x>>y;
if(mp[x][y]==0){ //避免重复的数据输入
mp[x][y]=1; //
in[y]++;//前驱数量加一
}
}topo();
}return 0;
}