拓扑排序-学习

·拓扑排序是什么呢？

我们先来看一下标准解释：

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

额，是不是有点懵……

其实，通俗易懂地说，拓扑排序就是在一个DAG中，对所有的节点进行排序，要求在序列中没有一个节点有边指向序列中它前面的节点。

·那么，我们该怎么去实现呢？

其实，求拓扑排序的过程，就是一个不断寻找入度为零的点和删边的过程。 如果一个点的入度为零，那么它一定可以直接被选（因为任何目前没有被选择的点都不可能在有边连向这一个点了）。每当我们选择一个点放入序列后，我们就要把所有以这个节点为起点的边都删掉，并更新其它点的入度。 tip：对于同一个图，拓扑排序后可能存在多种合法答案。 附一下代码：

#include<iostream>
   #include<cstring>
   #include<cstdio>
   #include<queue>
   
   using namespace std;
   
   queue<int>que;  //拓扑排序的过程也不一定用队列去实现 
   
   int t,n,m,x,y,cnt,d[100005],k[100005],ans[100005];
   
   struct Edge{
       int to,next;
   }edge[100005];
   
   void add(int x,int y)
   {
       edge[++cnt].to = y;
       edge[cnt].next = d[x];
       d[x] = cnt;
       k[y] ++;
   }
   
   void work()
   {
       for(register int i = 1; i <= n; i++) if(k[i] == 0) que.push(i);  //将所有入度为0的点入队 
       //cout << que.top()<<endl;
       while(!que.empty())
       {
           x = que.front();  //取队首元素 
           ans[++cnt] = x; //ans记录答案 
           que.pop();
           for(register int i = d[x]; edge[i].to != 0; i = edge[i].next)
           {
               k[edge[i].to] --;  //更新其它节点的入度 
               if(k[edge[i].to] == 0) //若入度为0，则将这个节点入队 
                   que.push(edge[i].to);
           }
       }
   }
   
   int main()
   {
       cin >> n >> m;  //表示有n个点，m条边 
       for(int i = 1; i <= m ;i++)  //存边 
       {
           cin >> x>>y;
           add(x,y);
       }
       cnt = 0;
       work();  //拓扑排序 
       for(register int i = 1; i <= n; i++) printf("%d ",ans[i]);
       return 0;
   }