拓扑序列

定义：拓扑序列是图中的顶点的线性排序，使得从顶点u到顶点v的每个有向边u->v ,在拓扑序列中u都在v前面

1. 不是所有的有向图都是有拓扑序的，只有有向无环图才有拓扑序，所以有向无环图又被称为拓扑图

2. 有向无环图的拓扑序不是唯一的

拓扑序列的求法

对于拓扑序列而言，入度为0的点一定是排在前面的
对一个图BFS一遍，BFS过程中更新每个点的入度，如果一个点的入度为0，那么就将其加入拓扑序，并且删除其与后继结点的所有边。

1.入度的计算

在建立邻接表时计算每个节点的入度
void add(int a,int b){
    e[idx] = b;
    d[b] ++; //节点b的入度加1
    
    ne[idx] = h[a];
    h[a] = idx;
    idx ++;
}

2. 得到拓扑序列

   bool topsort(){
       int hh=0,tt=-1;
       //先将目前入度为0的节点入队
       for(int i=1;i<=n;i++){
           if(d[i] == 0){
               q[++tt] = i;
           }
       }
       while(hh <= tt){
           int t = q[hh];
           hh++;
           //删除由节点t所指出的边（并不是真的删除，而是将节点入度减1）
           for(int i=h[t];i!=-1;i=ne[i]){
               int j = e[i];
               d[j] --; //该边的终点入度减1
               if(d[j] == 0){
                   q[++tt] = j; //让入度为0的节点入队
               }
           }
       }
       //判断是不是拓扑序列
       //如果所有点都入队了（所有点的入度都为0）就是拓扑序列，反之就不是
       return tt == n-1; //tt初始化时为-1，tt代表节点下标从0开始，因此是与n-1对比
   }

3. 判断是不是拓扑序列
   看队尾指针tt的值 加1 （下标从0开始）是不是等于节点个数

   //判断是不是拓扑序列
   //如果所有点都入队了（所有点的入度都为0）就是拓扑序列，反之就不是
   return tt == n-1; //tt初始化时为-1，tt代表节点下标从0开始，因此是与n-1对比

4. 输出拓扑序列
   由于出队只是将指针向后移动，但前面入队的元素还在队列数组中

   for(int i=0;i<n;i++){
       cout << q[i] << " ";
   }