#define Maxsize 20
#include "stdio.h"
#include"malloc.h"
typedef  struct node
{   
        int in,adjvex;
        struct node *next;
}JD;

typedef  struct tnode
{
        int in,vexdata;
        struct node *firstarc;
}TD;
TD g[Maxsize];int n;

void create(TD g[])
{
    int i,j,a,b;
    JD *p;
    printf("输入顶点数：");
    scanf("%d",&n);
    for(j=1;j<=n;j++)
    {
        g[j].vexdata=j;
        g[j].in=0;
        g[j].firstarc=NULL;
    }
    printf("输入边数：");
    scanf("%d",&i);
    for(j=1;j<=i;j++)
    {
        printf("输入边信息：");
        scanf("%d,%d",&a,&b);
        p=(JD*)malloc(sizeof(JD));
        p->adjvex=b;
        p->next=g[a].firstarc;
        g[a].firstarc=p;
    }
}


/*求每个顶点的入度*/
void out_degree(TD g[],int n,int v[])
{
    int i;
    JD *r;
    for(i=1;i<=n;i++)
    {
        r=g[i].firstarc;
        while(r!=NULL)
        {
            v[r.in]++;r=r->next;
        }
    }
}

/*拓扑排序*/
void topsort(TD g[],int l)
{
    int s[20],top,m,j,k;
    JD *p;
    top=0;
    m=0;
    for(j=1;j<=l;j++)
        if(g[j].in==0)
            s[top++]=j;
        while(top>0)
        {
            j=s[--top];
            printf("%d",g[j].vexdata);
            m++;
            p=g[j].firstarc;
            while(p!=NULL)
            {
                k=p->adjvex;
                g[k].in--;
                if(g[k].in==0)
                    s[top++]=k;
                p=p->next;
            }
        }
}


/*/*深度优先遍历
void dfs(TD g[],int v,int visited[])
{
    JD *w;
    int i;
    printf("%d",v);
    visited[v]=1;
    w=g[v].firstarc;
    while(w!=NULL)
    {
        i=w->adjvex;
        if(visited[i]==0)
            dfs(g,i,visited);
        w=w->next;
    }
}

/*深度优先遍历
void traver(TD g[],int n)
{
    int i;
    int visited[Maxsize];
    for(i=1;i<=n;i++)
       visited[i]=0;
    for(i=1;i<=n;i++)
      if(visited[i]==0)
              dfs(g,i,visited);
}

/*广度优先遍历
void bfs(TD g[],int v,int visited[])
{
    int qu[20],f=0,r=0;
    JD *p;
    printf("%d",v);
    visited[v]=1;
    qu[0]=v;
    while(f<=r)
    {
        v=qu[f++];
        p=g[v].firstarc;
        while(p!=NULL)
       {
            v=p->adjvex;
            if(visited[v]==0)
            {
                visited[v]=1;
                printf("%d",v);
                qu[++r]=v;
            }
            p=p->next;
       }
    }
}

/*广度优先遍历
void traver1(TD g[],int n)
{
    int i;
    int visited[Maxsize];
    for(i=1;i<=n;i++)
       visited[i]=0;
    for(i=1;i<=n;i++)
      if(visited[i]==0)
              bfs(g,i,visited);
}*/

main( )
  {     
    int a;
    int v[Maxsize]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    do
    {
        printf("\n");
        printf("***********************************");
        printf("\n");
        printf("\t\t1:建立邻接表:\n");
        printf("\t\t2:每个顶点的入度:\n");
        printf("\t\t3:  拓扑排序:\n");
        printf("\t\t0:  退出:\n");
        printf("***********************************\n"    );
        printf("\t");
        printf("请选择:");
         scanf("%d",&a);
        printf("\n");
        switch(a)
        {
            case 1: create(g); break;
            case 2: out_degree(g,n,v); break;
            case 3: topsort(v,n);break;
            case 0: exit(0);
            default:printf("输入错误,重输!\n");break;
         }
    }while(1);
}