#include<stdio.h>
#include<stdlib.h>

#define NULL 0
#define MAXV 100

typedef struct node
{int adjvex;
 struct node *next;
}ENode;
 
typedef struct
{char data;
struct ENode *firstedge;
}VNode;

typedef struct
{int n,e;
 VNode adjlist[MAXV];
}ALGraph;

void createalgraph(ALGraph *g)
{ENode *p;
 int i,j,k;
 char n,m;

 printf("Please enter the vexnum and arcnum:");
 scanf("%d%d",&g->n,&g->e);
 for(k=0;k<g->n;k++)
   {
    printf("\nPlease enter the info vex:");
    scanf(" %c",&g->adjlist[k].data);
    g->adjlist[k].firstedge=NULL;   
   }
 
 for(k=0;k<g->e;k++)
   {int x=0,y=0;
    printf("\nPlease enter two vex info:");
    scanf(" %c,%c",&n,&m);
    while(g->adjlist[x].data!=n)x++;
    while(g->adjlist[y].data!=m)y++; 
    i=x;
    j=y;
    p=(ENode*)malloc(sizeof(ENode));
    p->adjvex=j;
    p->next=g->adjlist[i].firstedge;
    g->adjlist[i].firstedge=p;
   }
}

int toposort(ALGraph *g,int q[])
{int top,m,j;
 int ind[MAXV];
 ENode *p;
 
 for(j=0;j<g->n;j++)ind[j]=0;
 for(j=0;j<g->n;j++)
   for(p=g->adjlist[j].firstedge;p;p=p->next)
      ind[p->adjvex]++;
 top=-1;m=0;
 for(j=0;j<g->n;j++)
   if(ind[j]==0)
     {ind[j]=top;top=j;}
 while(top>-1)
   {q[m++]=top;
    p=g->adjlist[top].firstedge;
    top=ind[top];
     while(p)
     {j=p->adjvex;
        if(--ind[j]==0)
        {ind[j]=top;top=j;}
        p=p->next;
     }
   }
 if(m<g->n)
 {printf("The AOV network has a cycle.\n");
  return(0);}
 else
 {
   printf("\nThe AOV network road is:");
   {for(m=0;m<g->n;m++)
    printf("%c",g->adjlist[q[m]].data);
   }
   return(1);
 }
}


main()
{ALGraph *g;
 int q[MAXV];
 g=(ALGraph*)malloc(sizeof(ALGraph));
 createalgraph(g);
 printf("\n**********************"); 
 toposort(g,q);

}