哦豁，先给个百度的定义吧

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

可能这个定义对于没有学过离散数学的人不太友好，偏序和全序是什么东西鸭摔
其实吧，不用看这个定义，其实这就是一个前驱和后继的关系，在实际关系中可以表现为某事是另外一件事的前提（依赖关系），比如你想要烧粥的前提是手上有米，并且有锅有火，这些条件都集齐才可以开始下一步：烧粥
v4事件的前提条件就是v1，v2的前提条件也是v1等等，我们就可以画出下面这有向图

image.png

下图和描述部分源网络

• 从DAG图中找到一个没有前驱的顶点输出。(可以遍历（比较笨，不推荐），最好用队列维护)
• 删除以这个点为起点的边。(它的指向的边删除，为了找到下个没有前驱的顶点)
• 重复上述，直到最后一个顶点被输出。如果还有顶点未被输出，则说明有环！

额外强调，拓扑排序只能用于有向无环图有向无环图有向无环图！！！用依赖关系来理解就是想要完成A必须先完成B，想完成B又必须先完成A，这就是死循环（环），是无法进行的！

对于上图的简单序列，可以简单描述步骤为：

• 1：删除1或2输出

  
  
  在这里插入图片描述

• 2：删除2或3以及对应边

  
  
  在这里插入图片描述

• 3：删除3或者4以及对应边
  在这里插入图片描述

• 3：重复以上规则步骤

  
  
  在这里插入图片描述

这样就完成一次拓扑排序，得到一个拓扑序列，但是这个序列并不唯一！从过程中也看到有很多选择方案，具体得到结果看你算法的设计了。但只要满足即是拓扑排序序列。

另外观察 1 2 4 3 6 5 7 9这个序列满足我们所说的有关系的节点指向的在前面，被指向的在后面。如果完全没关系那不一定前后(例如1,2)

image.png

这里的关系就是一个相对位置的关系，从而构成了一张图
那我们怎么能从这张图中求出答案，首先我们知道，以自己为终点最少可以游览一个城市，也就是自己，那么如何可以做到游览更多的城市，当然是从没有前驱或者说是已知的最西边的城市开始走了，也就是入度为0的点，然后拓扑排序用dp（动态规划）的思想不断更新len[i]（len[i]表示以i为终点最多能游览的城市数）代码走起

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>//拓扑排序需要
using namespace std;
struct xing
{
    int qian,wei;
}bian[210000];
int n,m,cnt,head[110000],len[110000],ru[110000],o1,o2;//链式前向星建图，len数组就是答案，ru这个数组表示每个点的入度
void add(int u,int v)
{
    bian[++cnt].qian=head[u];
    bian[cnt].wei=v;
    head[u]=cnt;
}//加边没啥说的
int main()
{
    cin>>n>>m;
    for(int i=1;i<m+1;i++)
    {
        cin>>o1>>o2;
        add(o1,o2);
        ru[o2]++;//记录一下每个点的入度
    }
    queue<int> q;//建立一个队列，用于维护入度为0的顶点，保证拓扑排序的进行
    for(int i=1;i<n+1;i++)
    {//初始化队列，先把所有入度为0的点扔进队列，顺便把len数组初始化了，毕竟初始值全是1
        if(!ru[i])
        q.push(i);
        len[i]=1;
    }
    while(!q.empty())
    {//当队列里啥都没有的时候，代表拓扑排序已经结束
        int u=q.front();//把队首提出来
        q.pop();//队首没用了，扔掉
        for(int i=head[u];i;i=bian[i].qian)
        {
            int v=bian[i].wei;//用有向边找下一个点
            ru[v]--;//因为此时u点已经从图里扔掉了，所以作为u的后继，节点v的入度自然要--
            len[v]=max(len[v],len[u]+1);//v可以作为从u点过来的终点，考虑到v可能不止一个前驱节点，所以用dp的思想，取那个最大的
            if(!ru[v])//如果v的前驱节点全部没了，那他自己就要进队了
            q.push(v);//进队
        }
    }
    for(int i=1;i<n+1;i++)
    cout<<len[i]<<"\n";//输出答案
    return 0;
}