2006-d-四

/**
    本题有各种答案，无论是学姐的还是红皮书都是错误的。
    正确思想在于采用拓扑排序，也是本题考点。深度优先搜索等无法解决。
**/
typedef struct VNode
{
    char data;
    int no;
    int count;
    ArcNode *firstarc;
}VNode;//重新定义邻接表表头结点

int TopSort(AGraph *G)
{
    int i,j ,n=0;
    int stack[maxSize],top=-1;//定义并初始化栈
    ArcNode *p;
    for(i=1;i<G->n;++i)
    {
        if(G->adjlist[i].count==0) stack[++top]=i;
    }
    while(top!=-1)
    {
        i=stack[top--];
        ++n;//计数器加1
        G->adjlist[i].no=n;//将整形序号赋值给结点
        p=G->adjlist[i].firstarc;
        while(p!=NULL)
        {
            j=p->adjvex;
            --(G->adjlist[j].count);
            if(G->adjlist[j].count==0) stack[++top]=j;
            p=p->nextarc;
        }
    }
    if(n==G->n)
        return 1;
    else
        return 0;
}