问题标题: 酷町堂微信公众号征文啦！！！征文啦！！

13
5
已解决
酷町猫
酷町猫
缔造者之神
缔造者之神

哒哒哒哒.......酷町喵过完暑假回来了呢....

童靴们有没有想念我呢？

酷町喵很想念大家呀..

大家暑假过的怎么样啊?老师布置的作业有没有完成啊？

酷町喵给大家带来了新的活动呢！！！喵喵喵~~让我来给大家介绍一下吧

酷町堂公众微信号征文开始了，想分享你的学习与生活吗？想展示一下自己的文采吗？想让大家看到你的文章吗？就让我酷町喵来见识一下你们的厉害吧！！！飒飒飒~~~

征稿时间：即日起长期征稿....除了酷町喵去吃小鱼干的时候 （不是我先动的手，是小鱼干！！！所以我只能代表正义与和平消灭它）

征稿内容：以计算机科学、算法竞赛、编程技术、学习生活为主，其余题材酌情接受，不接受专业性太强的文章（例如题解，除非能把算法知识说得通俗易懂），符合主流价值观，关键的一点哦。。。。说三遍，说三遍，说三遍，内容必须是原创！！必须是原创！！！原创！！！如果抄袭将会有很严重的后果吼  大家要跟酷町猫一样做个正义诚实的好孩子，不然的话我就会  恶喵咆哮 ...喵呜！喵呜！！

投稿方式：大家可以发WORD文档到我的邮箱，邮箱地址：kudingmiao@163.com

奖励：一经采纳，将会送出一份吃鸡游戏小挂件，欢迎大家投稿

大家如果有什么好的想法，欢迎踊跃留言。。。

酷町堂微信公众号，扫描二维码即可关注哦

举报

30酷町豆 刷题求解 14条评论 6 年，2 月 前

14
已采纳
陆麟瑞
陆麟瑞
资深天翼
资深天翼

投稿：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追加了内容

好像大家的积极性不高啊，这几天没几个人投稿。

阅读更多
举报

6 年，2 月 前 11条评论

5
2
郑怡翔
郑怡翔
初级天翼
初级天翼

文章准备好了，怎么投稿？

直接发在微信号上吗？

阅读更多
举报

6 年，2 月 前 2条评论

2
张瑀涵
张瑀涵
高级光能
高级光能

 能不能将采纳的文章也在酷町问答里置顶几天，直到下一篇文章被采纳

阅读更多
举报

6 年，2 月 前 1条评论

2
梁彦博
梁彦博
初级光能
初级光能

@陆麟瑞 

帮你的文章做了个图

拿走不谢

源码

$\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即可，把每个点的入度用一个一维数组来存储。如果您不是很理解，我们不妨先画一个图。

![lulinrui666](https://cdn.luogu.org/upload/pic/28141.png)

以上这幅图中入度为0的点为1和6（没有边指向1与6），我们就把1号点和6号点放入一个队列当中。学过BFS的同学都知道，一般写BFS的时候都要用到队列（数据结构队列在这里作者不在阐述，不知道的话可以自行百度）。

然后我们拿出队列中的首项v，这是就可以放心大胆地输出这个点的序号了，因为现在的图中不存在一条边的终点是v，比它优先级高的点要么已经输出过了，要么就不存在，接着我们要对v做一次牺牲，让这个点“与世隔绝”，就是把所有以它自己为起点的边全部删掉，如上图所示，如果v为1，就把从1至3的这条边删掉。变成了下图。

![lulinrui666](https://cdn.luogu.org/upload/pic/28140.png)

当每次删完一条边之前，我们还要把这条变得终点编号的入度减一（因为这条边已经被删了），这是我们还要判断，如果这是终点的入度为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，只是一个普通的有向图，这时我们拓扑排序时需要判环，简单画个有环的例子。

![lulinrui666](https://cdn.luogu.org/upload/pic/28141.png)

如上图所示，点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

 

阅读更多
举报

6 年，2 月 前 7条评论

2
梁彦博
梁彦博
初级光能
初级光能

话说奖励能换成酷町豆吗

阅读更多
举报

6 年，2 月 前 7条评论

1
李庚午
李庚午
中级守护
中级守护

天哪……继某咕咕日报之后，CTD也要搞日报……

阅读更多
举报

6 年，2 月 前 9条评论

1
蒋智航
蒋智航
高级天翼
高级天翼

🐱o(=•ェ•=)m；

请问您要这个是干嘛的呐？

若急需，我有一篇；

我正在疯狂打字中……

蒋智航在2018-08-26 17:48:20追加了内容

你邮箱多少，我邮箱发给你

蒋智航在2018-08-27 14:23:42追加了内容

什么是吃鸡挂件；

我基本不玩游戏，是好学的知识分子

阅读更多
举报

6 年，2 月 前 7条评论

1
1
1
蒋智航
蒋智航
高级天翼
高级天翼

@酷町喵~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~ 我要疯了，请问您收到了吗？

阅读更多
举报

6 年，2 月 前 7条评论

1
梁锦程
梁锦程
高级光能
高级光能

写了一篇很垃圾的文章，传给了@酷町喵~o( =∩ω∩= )o~QAQ

 

阅读更多
举报

6 年，2 月 前 2条评论

1
0
郑怡翔
郑怡翔
初级天翼
初级天翼

为什么找不到网页：kudingmiao@163.com

阅读更多
举报

6 年，2 月 前 2条评论

0
0
王光裕
王光裕
资深光能
资深光能

话说奖励能换成酷町豆吗

阅读更多
举报

6 年，2 月 前 0条评论

0
0
0
0
0
0
0
0
0
0
0
0
傅文彬
傅文彬
新手天翼
新手天翼

@所有人，加油努力为了吃鸡挂件！！！

阅读更多
举报

6 年，1 月 前 0条评论

0
陈子伟
陈子伟
初级守护
初级守护

写了1分宗的垃圾文稿，准备投

陈子伟在2018-09-21 15:26:00追加了内容

谢谢

阅读更多
举报

6 年，2 月 前 1条评论

0
0
0
0
0
0
0
时梓繁
时梓繁
修练者
修练者

兄弟们加油！！！我看好你们！！！

阅读更多
举报

6 年，2 月 前 0条评论

0
0
棠梨煎雪
棠梨煎雪
中级守护
中级守护

像洛谷日报(那个东西,嗯,投稿通过难度有点高,我在学学才可以通过)

阅读更多
举报

6 年，2 月 前 1条评论

0
0
周思睿
周思睿
新手光能
新手光能

哦，不，继洛谷日报与文文新闻之后的又一个日报……（chen_zhe，你够了！）

阅读更多
举报

6 年，2 月 前 0条评论

0
0
0
王骋恺
王骋恺
初级守护
初级守护

加油努力为了吃鸡挂件

阅读更多
举报

6 年，1 月 前 0条评论

0
0
0
张睿杰
张睿杰
初级天翼
初级天翼

@酷町喵~o( =∩ω∩= )o~ 这是你吗

阅读更多
举报

6 年，2 月 前 1条评论

我要回答
© 2021 酷町堂教育机构 版权所有 皖ICP备16015773号-1