/*拓撲排序*/
#include <stdio.h>
#include <malloc.h>
    #define M 10
    #define MAXVEX 10
    typedef char VertexType;
    
 struct edgenode
{   int vex;    /*鄰接點序號*/
    struct edgenode *next;   /*指向下一條弧的指針*/
};
 struct tnode
{   int vexdata;    /*頂點信息*/
    int in;
    struct edgenode *link;     /*指向第一條依附該頂點的弧的指針*/
}; 
typedef struct tnode adjlist[MAXVEX];
    void creagraph(adjlist g,int *n)   /*建立有向圖的鄰接表*/
    {
      int e,i,s,d;
      struct edgenode *p;
      printf("頂點數(shù)(n),弧數(shù)(e):");
      scanf("%d,%d",n,&e);
      for (i=1;i<=*n;i++)
      {
	getchar();
	printf("  第%d個頂點信息:",i);
	scanf("%d",&g[i].vexdata);
	g[i].link=NULL;
      }
      for (i=1;i<=*n;i++)       /*初始化，使各頂點入度為"0"*/
      {
		  g[i].in=0;
	  }
      for (i=1;i<=e;i++)
      {
	printf("第%d條弧=>起點序號,終點序號:",i);
	scanf("%d,%d",&s,&d);
	p=(struct edgenode *)malloc(sizeof(struct edgenode));	
	p->vex=d;
	g[d].in++;
	p->next=g[s].link;  /*p插入頂點s的鄰接表中*/
	g[s].link=p;
      }
    }
void toposort(adjlist g,int n)        /*拓撲排序*/
{  int top,m,k,j,s[M];     /*建立“0”入度頂點棧s*/
   edgenode *p;
   top=0; m=0;
   for(j=1;j<=n;j++)
     if(g[j].in==0)
       s[top++]=j;       /*入度為“0”者進棧*/
   while(top>0)
   {  j=s[--top];
      printf("%d  ",g[j].vexdata);
      m++;          /*對輸出頂點計數(shù)*/
      p=g[j].link;
      while(p!=NULL)   /*對j號頂點的每個鄰接點的入度減1*/
      {  k=p->vex;   
	 g[k].in--;
	 if(g[k].in==0)
	    s[top++]=k;      /*若入度減為0，則入棧*/
	 p=p->next;
      }
   }
   printf("\nm=%d\n",m);
   if(m<n)  printf("The network has a cycle\n");
}
main()
   {
      adjlist g;
      int n;  
      creagraph(g,&n);
      toposort(g,n);
}