前置芝士

BFS，别告诉我连这个都不会。

算法介绍

定义

数学上的：

将DAG中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。
通俗一点：
用宽搜一层层把图切开。
前提：图是一个DAG（有向无环图）

解决什么问题

假设有一些工作，完成某个工作的前提需要完成另某个工作，称为准备工作，至少一个工作不需要任何准备工作，至少一个工作不是任何工作的准备工作。
表示这种关系的图称为AOV网。用topo排序解决此类问题。

算法思路

文字思路

1. 将入度为0的点扔进队
2. 遍历这些点，将每个点所连的边炸掉，相当于所通向的点入度-1
3. 如果发现有点入度变为0则扔进队
4. 队列为空，算法结束，每次从队中取出元素的顺序就是一个合法的拓扑序

伪代码展示

int n;
vector<int>gragh[maxn];
int in[maxn];
for(int i=1;i<=n;i++){
    if(!in[i])q.push(i);
}
while(!q.empty()){
    int now=q.front();q.pop();
    printf("%d\n",now);
    for(int i=0;i<gragh[now].size();i++){
        in[gragh[now][i]]--;
        if(!in[gragh[now][i]]){    
       	    q.push(gragh[now][i]);
	}
    }
}