1.AOV与DAG
活动网络可以用来描述生产计划、施工过程、生产流程、程序流程等工程中各子工程的安排问题。
一般一个工程可以分成若干个子工程，这些子工程称为活动（Activity）。完成了这些活动，整个工程就完成了。例如下图的代表的计算机专业课程，学习就是一个工程，每门课程的学习就是整个工程中的一个活动。
我们可以用上图的有向图来表示课程之间的先修关系。在这种有向图中，顶点表示课程学习活动，有向边表示课程之间的先修关系。例如顶点C1到C8有一条有向边，表示课程C1必须在课程C8之前先学习完。
实际上，在这种有向图中，用顶点表示活动，用有向边表示活动u必须先于活动v进行。这种有向图叫做活动网络（Activity on Vertices），记做AOV网络。
前驱与后继：在AOV网络中，如果存在有向边，则称活动u必须在活动v之前进行，并称u是v的直接前驱，v是u的直接后继。如果存在有向路径，则称u是v的前驱，v是u的后继。
有向环与有向无环图：从前驱与后继的传递性和反自反性可以看出，AOV网络中不能出现有向回路（或称为有向环）。不含有向回路的有向图称为有向无环图(DAG, Directed Acyclic Graph)。
在AOV网络中如果出现了有向回路，则意味着某项活动以自己作为先决条件，这是不对的。
2.拓扑排序
判断有向无环图的方法是对AOV网络构造它的拓扑有序序列。即将各个顶点排列成一个线性有序的序列，使得AOV网络中所有存在的前驱和后继关系都能得到满足。
这种构造AOV网络全部顶点的拓扑有序序列的运算称为拓扑排序(Topological Sorting)。
如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV网络中必定不存在有向环；相反，如果得不到所有顶点的拓扑有序序列，则说明该AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。
例如对上图所示的学生选课工程图进行拓扑排序，得到的拓扑有序序列为：
C1，C2，C3，C4，C5，C6，C8，C9，C7
或者
C1，C8，C9，C2，C5，C3，C4，C7，C6
由此可见，AOV网络的拓扑有序序列可能不唯一。
3.Kahn算法拓扑排序算法：
（1）从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它；
（2）从网中删去该顶点,并且删去从该顶点发出的全部有向边；
（3）重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止。
输入：
6 8
1 2
1 4
2 6
3 2
3 6
5 1
5 2
5 6
1 2
1 4
2 6
3 2
3 6
5 1
5 2
5 6
6 8
1 3
1 2
2 5
3 4
4 2
4 6
5 4
5 6
输出：
Great! There is not cycle.
5 1 4 3 2 6
5 1 4 3 2 6
Network has a cycle!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<sstream>
#include<functional>
using namespace std;
typedef long long ll;
const int maxn = + ;
const int INF = 1e9 + ;
int T, n, m, cases;
vector<int>Map[maxn];
int Count[maxn];
void topo()
{
stack<int>s;//存储入度数为0的顶点
vector<int>v;//存取拓扑排序的答案
for(int i = ; i <= n; i++)//下标从1开始
if(Count[i] == )s.push(i);
while(!s.empty())
{
int now = s.top();
v.push_back(now);
s.pop();
for(int j = ; j < Map[now].size(); j++)
{
if((--Count[Map[now][j]]) == )
{
s.push(Map[now][j]);
}
}
}
if(v.size() != n)cout<<"Network has a cycle!"<<endl;
else
{
cout<<"Great! There is not cycle."<<endl;
for(int i = ; i < v.size(); i++)cout<<v[i]<<" ";
cout<<endl;
}
}
int main()
{
while(cin >> n >> m)
{
if(!n && !m)break;
int u, v;
for(int i = ; i <= n; i++)Map[i].clear();
memset(Count, , sizeof(Count));
for(int i = ; i < m; i++)
{
cin >> u >> v;
Map[u].push_back(v);
Count[v]++;//存入度
}
topo();
}
return ;
}
时间复杂度：由于每个点入栈出栈一次，每条边扫描一次，时间复杂度为O(m + n)