//AOV网与拓扑排序类

 #ifndef _AOV_H_

 #define _AOV_H_

 #include<iostream>

 #include<cstdio>

 #include<malloc.h>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 using namespace std;

 #endif

 struct point

 {

     int vertex;//顶点

     point* next;

 };

 class AOV

 {

     private:

     int* ok;

     int* indegree;//入度

     point* aim;//邻接表

     bool n_hasvalue;

     int n;

     public:

     int* ans;

     AOV(int maxn,int point_num);//构造函数原型

     AOV():AOV(,){};//直接构造函数

     AOV(int maxn);//容器型构造参数

     void maxpoint(int p);

     int readin();

     int* topo_sort();

 };

 void AOV::maxpoint(int p)

 {

     if(n_hasvalue==true)

     {

         printf("Sorry n had value,ERROR!\n");

         return;

     }

     n=p;

     n_hasvalue=true;

     return;

 }

 AOV::AOV(int maxn)//容器型构造参数

 {

     ans=new int[maxn];

     ok=(int*)new int[maxn];

     memset(ok,,sizeof(int)*maxn);

     //这里的重置不能写成sizeof(ok);

     indegree=new int[maxn];

     aim=new point[maxn];

     n_hasvalue=false;

 }

 AOV::AOV(int maxn,int point_num)

 {//maxn描述可能使用到的最大的顶点数量

     ans=new int[maxn];

     ok=(int*)new int[maxn];

     memset(ok,,sizeof(int)*maxn);

     indegree=new int[maxn];

     aim=new point[maxn];

     n_hasvalue=true;

     n=point_num;

 }

 int AOV::readin()

 {

     if(n_hasvalue==false){printf("n do not has value!\n");return ;}

     memset(indegree,,sizeof(int)*(n+));

     for(int i=;i<n;i++)

     {

         aim[i].next=NULL;

         aim[i].vertex=i;

     }

     //初始化

     int a,b;

     //printf("Please input pairs of numbers, which from 0 to n-1, to describe the relationship.\n");

     //printf("When there is a pair of numbers consists of two 0,then input will stop.\n");

     while(cin>>a>>b)

     {//a->b

         if(a==&&b==)break;

         if(a>=n||b>=n||a<||b<){printf("Data error\n");continue;}

         indegree[b]++;//入度加1

         point* temp=&aim[a];

         while(temp->next!=NULL)temp=temp->next;

         //找到存有指向结点链表的末端

         temp->next=(point*)malloc(sizeof(point));

         temp=temp->next;//进入新的point点

         temp->vertex=b;//a->b

         temp->next=NULL;

     }//完成邻接表的构建

     return ;

 }

 int* AOV::topo_sort()

 {

 //    for(int i=0;i<n;i++)

 //    {

 //        printf("vertex %d indegree %d points to:",aim[i].vertex,indegree[i]);

 //        point* temp=&aim[i];

 //        while(temp->next!=NULL)

 //        {

 //            temp=temp->next;

 //            printf("%d ",temp->vertex);

 //        }

 //        printf("\n");

 //    }

     queue<int> psd;

     int cur=;

     int num=n;

     while()

     {

         if(num)

         {

             for(int i=;i<n;i++)

             {

                 if(ok[i])continue;

                 if(indegree[i]==)

                 {

                     psd.push(i);

                     ok[i]=;

                     num--;

                 }

             }//检查所有入度0的顶点并入队,留下入队标记

         }

         if(psd.empty())break;//队列为空则排序结束

         int p=psd.front();psd.pop();

         point* temp=&aim[p];

         ans[cur++]=p;//也可以写成ans[cur++]=aim[i].vertex;

         //printf("%d ",p);

         //提出结点并排序

         while(temp->next!=NULL)

         {

             temp=temp->next;

             indegree[temp->vertex]--;

         }//去掉相关有向边

     }

     //printf("\n\ncur->%d\n",cur);

     return ans;

 }