初识AOV拓扑排序

首先先引入一段概念：

AOV网：

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系。这样的有向图为顶点表示活动的网，我们称为AOV网（Activity On Vertex Network）。

程序设计语言（以C语言为例）中定义为：在一个有向图中，若用顶点代表活动，边代表活动间先后关系，称该有向图为顶点活动网，简称AOV网。在AOV网中，若从顶点i到顶点j之间存在一条有向路径，称顶点i是顶点j的前驱，或者称顶点j是顶点i的后继。若

现在大家既然已经明白什么是AOV网，那么下面让我们来脑补一波拓扑排序：

拓扑排序算法，只适用于AOV网（有向无环图）

把AOV网中的所有活动排成一个序列（就是事情的先后顺序），使得每个活动的前驱总在当前活动的前面，后继在他的后面，这个过程叫做拓扑排序，所得到的序列叫做拓扑序列！

下面放两张图，大家可以脑补一下：

下面一张更形象：

大家在理解代码的时候，可以认真看一下第二张图片：

#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
int n;
stack<int> ans;//定义栈 //也可以使用队列！！！ 
vector<int > son[];//每个人存储的儿子 
int enter[];//存储儿子的爸爸的入度。 
void init();
int main()
{
    int flag=;
    init();
    for(int i=;i<=n;++i)
    {
        if(enter[i]==)//如果入度为0，入栈！ 
        {
            ans.push(i);
        }
    }
    while(flag<n)//如果没有找够人，就找！！！ 
    {
        int now=ans.top();
        printf("%d ",now);//输出入度为零的点now 
        ans.pop();
        flag++;
        for(int i=son[now].size()-;i>=;--i)//把now的儿子的入度-1 
        {
            enter[son[now][i]]--;
            if(enter[son[now][i]]==)//如果儿子身上入度为0， 入栈！！！ 
            {
                ans.push(son[now][i]);
            }
        }
    }
    return ;
}
void init()//读入操作 
{
    scanf("%d",&n);
    int a;
    for(int i=;i<=n;++i)
    {
        while()
        {
            scanf("%d",&a);
            if(a==)
            break;
            else
            son[i].push_back(a);
            enter[a]++;
        }
    }
}