算法小讲堂之拓扑排序

拓扑排序 一、前言

AOV网：若用 D A G DAG DAG 图表示一个工程，其顶点表示活动，用有向边 ＜ V i , V j ＞ ＜V_i ,V_j＞ ＜Vi​,Vj​＞ 表示活动 V i V_i Vi​ 只必须先于活动 V j V_j Vj​ 进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为 A O V AOV AOV 网

将一个 有向无环图（DAG）所有顶点线性化的算法就是 拓扑排序 ，当然啦这个序列显然满足以下两个条件：

• 图中每个顶点仅出现一次
• 若点 A A A 在图中有一个指向点 B B B 的弧，那么在序列中 A A A 一定在 B B B 的前面

二、原理

对于一个 A O V AOV AOV 网我们进行排序的算法有很多，这里主要介绍 K a h n Kahn Kahn 算法，算法步骤如下：

• ①从 A O V AOV AOV 网中选择一个没有前驱的顶点（ 入度为0 ）并输出
• ②从 A O V AOV AOV 网中 删除 该顶点以及该顶点相关的有向边
• 重复步骤①、②直到当前的 A O V AOV AOV 网为空 或者当前网中 不存在无前驱的结点 为止，而后一种情况就说明了图中存在环

举个例子，假设有如下的 D A G DAG DAG 图： 我们可以看到在第一轮删除了①号结点，然后接着是②、④、③、⑤，每次删除结点以及和这个结点相关的边，都会让这个结点指向的下一个结点的入度减一

注意：一个 D A G DAG DAG 图可能存在多个拓扑排序，例如下图的拓扑排序 我们发现这里的拓扑排序可能是： [ ①、②、③、④、⑤ ] [①、②、③、④、⑤] [①、②、③、④、⑤] 也有可能是 [ ①、③、②、④、⑤ ] [①、③、②、④、⑤] [①、③、②、④、⑤]

三、代码实现

从上面的步骤来看，这个拓扑排序需要记录每个点的度数，我们可以用一个数组 d d d 记录每个点的入度，读完图后（读图的过程中记录每个点的入度），我们将入度为 0 0 0 的点先放入队列 que 中，然后不断地取出队首元素，并放进我们的序列数组ans中，然后将队首元素出度的边都删掉，也就是将边连接的这些点的入度减一，如果发现入度减为 0 0 0 了，那么就将这个点加入队列中，然后重复这个操作就能得到拓扑排序的结果啦

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f
const int N = 2e6+10;
//----------------自定义部分----------------
int n,m,q,d[N],vis[N];
vector V[N],ans;

bool topsort(){
	queue que;
	for(int i = 1;i