拓扑排序

概念

AOV网

1. 一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。

2. 一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。如图3-6是一个具有三个顶点的回路，由A -> B边可得B活动必须在A活动之后，由B -> C边可得C活动必须在B活动之后，所以推出C活动必然在A活动之后，但由C -> A边可得C活动必须在A活动之前，从而出现矛盾，使每一项活动都无法进行。这种情况若在程序中出现，则称为死锁或死循环，是应该必须避免的。

3. 在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列

求解方法

1 . 判环，有环的DAG不可能有拓扑序列，因此本身可用来判环，也可用tarjan与深搜，这里介绍深搜.vis[i] = {0,1,-1};0表示未访问，1表示已访问，-1表示正在访问栈中，深搜时如果遇见访问栈中的点，说明有环；该点未访问但搜下去有环也返回false；

inline bool topddfs(int x) {
    vis[x] = -1;
    for(rint i = head[x];i;i = e[i].last) {
        if(vis[e[i].to] == -1) return 0;
        if(!vis[e[i].to] && !topddfs(e[i].to)) return 0;
    }
    vis[x] = 1;
    return 1;
}

2 . 遍历所有点，把入度为0的点放入队列中；
3 . 每次从队列中取出点，把该点所指向的点的入度-1（即是删除该点指向其他点的边），如果被指向的点入度也变为0，放入队列，重复至队列为空。
4 . 第3步更新时使用pre[]记录某点的先驱，把序列导入数组时可采用递归或循环

inline void gt(int x) {//递归
        if(x == 0) return ;
        gt(pre[x]);
        ans[++top] = x;
}
while(xb) {//循环
        ans[++top] = xb;
        xb = pre[xb];
}//注意，两种方法得到的序列顺序不同

拓扑排序

原文：https://www.cnblogs.com/Thomastine/p/11733626.html