缔造者之神
哒哒哒哒.......酷町喵过完暑假回来了呢....
童靴们有没有想念我呢？
酷町喵很想念大家呀..
大家暑假过的怎么样啊?老师布置的作业有没有完成啊？
酷町喵给大家带来了新的活动呢！！！喵喵喵~~让我来给大家介绍一下吧
酷町堂公众微信号征文开始了，想分享你的学习与生活吗？想展示一下自己的文采吗？想让大家看到你的文章吗？就让我酷町喵来见识一下你们的厉害吧！！！飒飒飒~~~
征稿时间：即日起长期征稿....除了酷町喵去吃小鱼干的时候 （不是我先动的手，是小鱼干！！！所以我只能代表正义与和平消灭它）
征稿内容：以计算机科学、算法竞赛、编程技术、学习生活为主，其余题材酌情接受，不接受专业性太强的文章（例如题解，除非能把算法知识说得通俗易懂），符合主流价值观，关键的一点哦。。。。说三遍，说三遍，说三遍，内容必须是原创！！必须是原创！！！原创！！！如果抄袭将会有很严重的后果吼
大家要跟酷町猫一样做个正义诚实的好孩子，不然的话我就会 恶喵咆哮 ...喵呜！喵呜！！
投稿方式：大家可以发WORD文档到我的邮箱，邮箱地址：kudingmiao@163.com
奖励：一经采纳，将会送出一份吃鸡游戏小挂件，欢迎大家投稿
大家如果有什么好的想法，欢迎踊跃留言。。。
酷町堂微信公众号，扫描二维码即可关注哦
资深天翼
投稿：https://www.luogu.org/blog/judgecodingtang/qian-tan-ta-pu-pai-xu
自己百分百原创，讲解拓扑排序，若有不足请指出。
陆麟瑞在2018-08-25 18:49:19追加了内容
马上将会初稿关于STL的文章。
陆麟瑞在2018-08-26 18:33:17追加了内容
好像大家的积极性不高啊，这几天没几个人投稿。
修练者
奖励能换成经验吗
初级天翼
文章准备好了，怎么投稿？
直接发在微信号上吗？
高级光能
能不能将采纳的文章也在酷町问答里置顶几天，直到下一篇文章被采纳
初级光能
@陆麟瑞
帮你的文章做了个图
源码
$\color{red} \text{特别说明转自陆麟瑞666奆佬！}$
##1. 什么是拓扑排序？
拓扑排序就是在一个有向无环图（也称DAG图），将所有的点进行排序，使得每条有向边的起点u都排在终点v的前面。
如果您觉得上述比较难理解，可以举一个简单的例子。比如，在洛谷中的试炼场，有一些有先决要求的任务，这些任务必须要先完成其他的任务才能做，因此要先完成以前的子任务才能去做，有先解决任务的优先级要比它的子任务要高，这种关系可以用一个有向图来表示。
假设一个有先决要求的任务为v,必须先要完成任务u，这时就可以建一条有向边，以u为起点，v为终点。通常，我们把这种点表示任务，边表示任务之间的前后顺序关系的有向图称为AOV网（Activity On Vertex network）。
##2.如何实现拓扑排序？
实现拓扑排序这里介绍两种算法，一种是DFS（深度优先搜索）和BFS广度优先搜索。
我们先来谈谈如何用BFS的方法。
① 先建图。这里本蒟蒻采用的是邻接表方法。用C++STL中的vector（当然也可用链式前向星）。读入两个点u,v。u是起点，v是终点，将v插入u的vector中，即G[u].push_back(v);这样第一步就做好了qwq
② BFS实现拓扑排序。首先我们找图中所有入度为0的点。（入度就是一个点被指向边的数量，一个有向无环图中一定存在一个入度为0的点）。那怎样才能统计入度？很简单，只要在刚才建图的过程中，把每条边终点v的入度加1即可，把每个点的入度用一个一维数组来存储。如果您不是很理解，我们不妨先画一个图。
以上这幅图中入度为0的点为1和6（没有边指向1与6），我们就把1号点和6号点放入一个队列当中。学过BFS的同学都知道，一般写BFS的时候都要用到队列（数据结构队列在这里作者不在阐述，不知道的话可以自行百度）。
然后我们拿出队列中的首项v，这是就可以放心大胆地输出这个点的序号了，因为现在的图中不存在一条边的终点是v，比它优先级高的点要么已经输出过了，要么就不存在，接着我们要对v做一次牺牲，让这个点“与世隔绝”，就是把所有以它自己为起点的边全部删掉，如上图所示，如果v为1，就把从1至3的这条边删掉。变成了下图。
当每次删完一条边之前，我们还要把这条变得终点编号的入度减一（因为这条边已经被删了），这是我们还要判断，如果这是终点的入度为0（删后没有边指向它了），那么我们就把这个点丢入队列中（做好下次输出并牺牲的准备）。
最后，一直循环以上的过程（敲黑板！！！），直到所有边都删完时，整个拓扑排序的过程已经结束了。思路并不复杂，下面贴代码qwq
```
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 1010
int in[MAXN];
vector<int>G[MAXN];//vector数组，头文件是#include<vector>
void topsort(int n)
{
queue<int>q;//定义一个队列，头文件是#include<queue>
for(int i=1; i<=n; i++)
if(!in[i]) q.push(i);//如果这个点的入度为0，就进入队列
while(!q.empty())//当队列不为空时就进行，想想为什么
{
int v=q.front();//取出队中的首项
q.pop();//并拿出
cout<<v<<' ';//这时候可以输出v点了
for(int i=0; i<G[v].size(); i++)//做出牺牲，删边
{
in[G[v][i]]--;//终点的入度减一
if(!in[G[v][i]])//如果终点入度为0
{
q.push(G[v][i]);//进入队列
}
}
}
}
int main()
{
int n,m;
cin>>n>>m;//读入
for(int i=1; i<=m; i++)
{
int u,v;
cin>>u>>v;
in[v]++;//v的入度+1
G[u].push_back(v);//建一条边
}
topsort(n);//拓扑排序
return 0;
}
```
##如何在拓扑排序时判环？
如果有时这个图不是一个DAG，只是一个普通的有向图，这时我们拓扑排序时需要判环，简单画个有环的例子。
如上图所示，点2,3,4构成了一个环.怎样判断环呢，还是很简单
的，按上面所说的过程运行，1节点牺牲时，发现3的入度并没有为0，而1已经牺牲了，另一个点2也到达不了，这样就永远也到达不
了3了QAQ，因为到达不了3，我们就可以判断这个图就是一个存在环的有向图。那怎样去实现呢？只要在以上程序中的while循环中
加一个tot计数器就OK了，每次从队列中拿出一个数时，tot加1，while循环结束的时候判断tot是否等于节点总数，若不等于，则说明图是有环的。
代码:
```
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 1010
int in[MAXN];
vector<int>G[MAXN];//vector数组，头文件是#include<vector>
int ans[MAXN];//存答案的数组
void topsort(int n)
{
int tot=0,size=0;
queue<int>q;//定义一个队列，头文件是#include<queue>
for(int i=1; i<=n; i++)
if(!in[i]) q.push(i);//如果入读为0，就进入队列
while(!q.empty())//当队列不为空时就进行，想想为什么
{
int v=q.front();//取出队中的首项
q.pop();//并拿出
tot++;
ans[++size]=v;//这是不能输出了，因为可能存在环
for(int i=0; i<G[v].size(); i++)//做出牺牲，删边
{
in[G[v][i]]--;//终点的入度减一
if(!in[G[v][i]])//如果终点入度为0
{
q.push(G[v][i]);//进入队列
}
}
}
if(tot==n)
{
for(int i=1; i<=size; i++)
cout<<ans[i]<<' ';
}
else
{
cout<<"No";//有环
}
}
int main()
{
int n,m;
cin>>n>>m;//读入
for(int i=1; i<=m; i++)
{
int u,v;
cin>>u>>v;
in[v]++;//v的入读+1
G[u].push_back(v);//建一条边,vector
}
topsort(n);//拓扑排序
return 0;
}
```
##有哪些拓扑排序的题目？
洛谷上的P3242（算是一道拓扑排序的水题，可能是假的紫题）
P1038 神经网络 一道很经典的拓扑排序题目
P2017 先拓扑排序单向道路，在比较每个双向道路起点终点的前后顺序
P4742 先用Tarjan缩点，然后用拓扑排序dp
PS：本人蒟蒻一枚，如果此文章有哪里说错了，欢迎在评论区里告诉作者qwq
初级光能
话说奖励能换成酷町豆吗
中级守护
天哪……继某咕咕日报之后，CTD也要搞日报……
高级天翼
🐱o(=•ェ•=)m；
请问您要这个是干嘛的呐？
若急需，我有一篇；
我正在疯狂打字中……
蒋智航在2018-08-26 17:48:20追加了内容
你邮箱多少，我邮箱发给你
蒋智航在2018-08-27 14:23:42追加了内容
什么是吃鸡挂件；
我基本不玩游戏，是好学的知识分子
高级光能
已投稿
初级启示者
https://blog.csdn.net/qq_43062741/article/details/82085112
这是本蒟蒻一篇很水的有关排序的文章，写了2天，准备投稿。
我不知道投稿网址在哪所以就直接发了
好像大家的积极性不高啊，这几天没几个人投稿。
高级天翼
@酷町喵~o( =∩ω∩= )o~ @酷町喵~o( =∩ω∩= )o~ @酷町喵~o( =∩ω∩= )o~ @酷町喵~o( =∩ω∩= )o~ @酷町喵~o( =∩ω∩= )o~ @酷町喵~o( =∩ω∩= )o~ @酷町喵~o( =∩ω∩= )o~ @酷町喵~o( =∩ω∩= )o~ @酷町喵~o( =∩ω∩= )o~ @酷町喵~o( =∩ω∩= )o~ \
收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？
我发了n多遍
至少发了20来遍
收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？收到了吗？
蒋智航在2018-08-31 11:35:41追加了内容
我很皮的
蒋智航在2018-08-31 11:37:52追加了内容
@酷町喵~o( =∩ω∩= )o~ 我要疯了，请问您收到了吗？
高级光能
写了一篇很垃圾的文章，传给了@酷町喵~o( =∩ω∩= )o~QAQ
初级启示者
写了2天，准备投稿
初级天翼
为什么找不到网页：kudingmiao@163.com
高级天翼
嗯？我都不知道
资深光能
话说奖励能换成酷町豆吗
高级光能
加油！
初级光能
收到
高级守护
加油！！！
中级光能
hehe
新手天翼
像洛谷日报
高级守护
no
高级守护
抄袭后果如何？
修练者
算了吧。
新手守护
加油
修练者
加油
修练者
加油
新手天翼
@所有人，加油努力为了吃鸡挂件！！！
初级守护
写了1分宗的垃圾文稿，准备投
陈子伟在2018-09-21 15:26:00追加了内容
谢谢
初级天翼
我们会积极投稿的
高级守护
奖励能换成酷町币吗
资深守护
加油↖(^ω^)↗
中级光能
已投稿
资深守护
资深守护
我没微信
修练者
兄弟们加油！！！我看好你们！！！
初级光能
准备投稿
中级守护
像洛谷日报(那个东西,嗯,投稿通过难度有点高,我在学学才可以通过)
初级天翼
已投稿
新手光能
哦，不，继洛谷日报与文文新闻之后的又一个日报……（chen_zhe，你够了！）
资深光能
知道了。
初级天翼
请问什么时间截止
初级守护
加油努力为了吃鸡挂件
初级光能
快写完了
高级守护
eee
初级天翼
@酷町喵~o( =∩ω∩= )o~ 这是你吗
