初識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]++;
        }
    }
}