#include<string.h>  
 #include<ctype.h>  
 #include<malloc.h> 
 #include<limits.h>  
 #include<stdio.h>   
 #include<stdlib.h>   
 #include<io.h>   
 #include<math.h>   
 #include<process.h>  
 #include<iostream.h>
 #include<string.h>
 #include<ctype.h>
  
 // 函數(shù)結(jié)果狀態(tài)代碼  
 #define TRUE 1  
 #define FALSE 0  
 #define OK 1  
 #define ERROR 0  
 #define INFEASIBLE -1  
 typedef int Status; // Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等
 typedef int Boolean;  //Boolean是布爾類型,其值是TRUE或FALSE 
 #define MAX_NAME 4   
 //頂點(diǎn)字符串的最大長度  
 #define MAXCLASS 100  
 int Z=0;  
 int X=0;
 int Y=0;
 int xqzs,q=1,xfsx; 
 int pd;
 typedef int InfoType;  
 typedef char VertexType[MAX_NAME]; //字符串類型 
 //圖的鄰接表存儲(chǔ)表示 
 #define MAX_VERTEX_NUM 100  
 typedef enum{DG}GraphKind; // {有向圖,有向網(wǎng),無向圖,無向網(wǎng)}   
 typedef struct ArcNode  
            {  
                int adjvex; // 該弧所指向的頂點(diǎn)的位置   
                struct ArcNode *nextarc; // 指向下一條弧的指針 
                InfoType *info; // 網(wǎng)的權(quán)值指針）    
 }ArcNode; // 表結(jié)點(diǎn)    
 typedef struct  
           {  
                VertexType data; // 頂點(diǎn)信息  
                ArcNode *firstarc; //第一個(gè)表結(jié)點(diǎn)的地址,指向第一條依附該頂點(diǎn)的弧的指針   
           }VNode,AdjList[MAX_VERTEX_NUM]; //頭結(jié)點(diǎn)  
 typedef struct  
           {  
                AdjList vertices,verticestwo,copy1,copy2;  
                int vexnum,arcnum; // 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)  
                int kind; // 圖的種類標(biāo)志  
           }ALGraph;  
//  圖的鄰接表存儲(chǔ)的基本操作    
 int LocateVex(ALGraph G,VertexType u)  
 { // 初始條件: 圖G存在,u和G中頂點(diǎn)有相同特征    
   // 操作結(jié)果: 若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1    
   int j;  
   for(j=0;j<G.vexnum;++j)  
     if(strcmp(u,G.vertices[j].data)==0)  
       return j;  
   return -1;  
}  
Status CreateGraph(ALGraph *G)  
 { // 采用鄰接表存儲(chǔ)結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的圖G(用一個(gè)函數(shù)構(gòu)造4種圖)    
   int i,j,k; 
   VertexType va,vb;  
   ArcNode *p; 
   printf("請輸入教學(xué)計(jì)劃的課程數(shù): ");  
   scanf("%d",&(*G).vexnum);  
   printf("請輸入拓?fù)渑判蛩纬傻恼n程先修關(guān)系的邊數(shù): ");  
   scanf("%d",&(*G).arcnum);  
   printf("請輸入%d個(gè)課程的代表值:\n",(*G).vexnum);  
   for(i=0;i<(*G).vexnum;++i) // 構(gòu)造頂點(diǎn)向量    
        { scanf("%s",(*G).vertices[i].data);  
          (*G).vertices[i].firstarc=NULL;  
        }  
   printf("請輸入%d個(gè)課程的學(xué)分值(<3個(gè)字符):\n",(*G).vexnum);  
   for(i=0;i<(*G).vexnum;++i) // 構(gòu)造頂點(diǎn)向量    
        {scanf("%s",(*G).verticestwo[i].data);  
        }  
   printf("請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");  
   for(k=0;k<(*G).arcnum;++k) // 構(gòu)造表結(jié)點(diǎn)鏈表    
       { scanf("%s%s",va,vb);  
         i=LocateVex(*G,va); // 弧尾    
         j=LocateVex(*G,vb); // 弧頭    
         p=(ArcNode*)malloc(sizeof(ArcNode));  
         p->adjvex=j;  
         p->info=NULL; // 圖    
         p->nextarc=(*G).vertices[i].firstarc; //插在表頭    
         (*G).vertices[i].firstarc=p;  
       }  
   return OK;  
 }  
void Display(ALGraph G)  
 { //輸出圖的鄰接矩陣G    
   int i;  
  ArcNode *p;  
   printf("%d個(gè)頂點(diǎn)：\n",G.vexnum);  
   for(i=0;i<G.vexnum;++i)  
     printf("%s ",G.vertices[i].data);  
   printf("\n%d條弧(邊):\n",G.arcnum);  
   for(i=0;i<G.vexnum;i++)  
       {  
         p=G.vertices[i].firstarc;  
         while(p)  
            {printf("%s→%s  ",G.vertices[i].data,G.vertices[p->adjvex].data);  
             p=p->nextarc;  
            }  
         printf("\n");  
       }  
 }  
void FindInDegree(ALGraph G,int indegree[])  
 { //求頂點(diǎn)的入度 
   int i;  
   ArcNode *p;  
   for(i=0;i<G.vexnum;i++)  
     indegree[i]=0; // 賦初值   
   for(i=0;i<G.vexnum;i++)  
     {  
      p=G.vertices[i].firstarc;  
      while(p)  
          { indegree[p->adjvex]++;  
            p=p->nextarc;  
          }  
     }  
 }  
 typedef int SElemType; // 棧類型    
 //棧的順序存儲(chǔ)表示    
 #define STACK_INIT_SIZE 10 // 存儲(chǔ)空間初始分配量   

#define STACKINCREMENT 2 // 存儲(chǔ)空間分配增量    
 typedef struct SqStack  
        {  
         SElemType *base; // 在棧構(gòu)造之前和銷毀之后，base的值為NULL    
         SElemType *top; // 棧頂指針    
         int stacksize; // 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位    
        }SqStack; //順序棧    
 // 順序棧的基本操作    
 Status InitStack(SqStack *S)  
 { // 構(gòu)造一個(gè)空棧S    
   (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));  
   if(!(*S).base)  
     exit(OVERFLOW); //存儲(chǔ)分配失敗    
   (*S).top=(*S).base;  
   (*S).stacksize=STACK_INIT_SIZE;  
   return OK;  
}  
Status StackEmpty(SqStack S)  
 { // 若棧S為空棧，則返回TRUE，否則返回FALSE    
   if(S.top==S.base)  
     return TRUE;  
   else  
     return FALSE;  
}  
Status Pop(SqStack *S,SElemType *e)  
 { // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR    
   if((*S).top==(*S).base)  
     return ERROR;  
   *e=*--(*S).top;  
   return OK;  
 }  
Status Push(SqStack *S,SElemType e)  
 { // 插入元素e為新的棧頂元素    
   if((*S).top-(*S).base>=(*S).stacksize) // 棧滿，追加存儲(chǔ)空間    
           {  
             (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof  (SElemType));  
             if(!(*S).base)  
             exit(OVERFLOW); // 存儲(chǔ)分配失敗   
             (*S).top=(*S).base+(*S).stacksize;  
             (*S).stacksize+=STACKINCREMENT;  
          }  
   *((*S).top)++=e;  
   return OK;  
 }  
typedef int pathone[MAXCLASS];  
typedef int pathtwo[MAXCLASS];  
Status TopologicalSort(ALGraph G)  
 { // 有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K,  
   // 否則返回ERROR。   
   int i,k,n=0,count,indegree[MAX_VERTEX_NUM];
   SqStack S;  
   pathone a;  
   pathtwo b;  
   ArcNode *p;  
   FindInDegree(G,indegree); // 對(duì)各頂點(diǎn)求入度
   InitStack(&S);
   for(i=0;i<G.vexnum;++i) // 建零入度頂點(diǎn)棧S   
     if(!indegree[i])  
       Push(&S,i); // 入度為0者進(jìn)棧   
   count=0; // 對(duì)輸出頂點(diǎn)計(jì)數(shù)   
   while(!StackEmpty(S))  
       { // 棧不空   
           Pop(&S,&i);  
           a[i]=*G.vertices[i].data;  
           b[i]=*G.verticestwo[i].data;
           printf("課程%s→學(xué)分%s  ",G.vertices[i].data,G.verticestwo[i].data);   
           // 輸出i號(hào)頂點(diǎn)并計(jì)數(shù)
          ++count; 
          strcpy(G.copy1[n].data,G.vertices[i].data);
          strcpy(G.copy2[n].data,G.verticestwo[i].data);
          ++n;
         for(p=G.vertices[i].firstarc;p;p=p->nextarc)  
            { // 對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1   
              k=p->adjvex;  
              if(!(--indegree[k])) // 若入度減為0,則入棧    
              Push(&S,k);  
            }
       }  
   if(count<G.vexnum)  
       {printf("此有向圖有回路\n");  
        return ERROR;  
       }  
   else  
       {printf("為一個(gè)拓?fù)湫蛄小n"); 
       } 
   if(pd==1)
	{printf("課程負(fù)擔(dān)均勻的方案為：\n");
	   while(q<=xqzs)
		{
	     Z=G.vexnum/xqzs;
	     printf("第%d個(gè)學(xué)期應(yīng)學(xué)課程:",q);
	     Y=Y+Z;
	     while(X<Y)
			{
		     printf("%s ", G.copy1[X].data);
		     X++;
			}
	     printf("\n");
	     q++;
		}
	}
   else 
	   if(pd==2)
		{printf("課程向前集中的方案為：\n");
		   while(q<=xqzs)   
			{
			 int C=0 ;  
             while(Z<G.vexnum)  
				{ 
                 C+=*G.copy2[Z].data-48;
                 if(C<=xfsx)
                   Z++;
                 else break;
				}
             printf("第%d個(gè)學(xué)期應(yīng)學(xué)課程:",q);
             while(X<=Z-1)
				{
	             printf("%4s",G.copy1[X].data);
	             X++;
				}
			 printf("\n");
             q++;
			} 
		}
	   else
		   printf("輸入錯(cuò)誤！\n");
if(pd==1||pd==2)		  
	{printf("課程編制已經(jīng)完成！");     
     return OK;
	}
printf("\n");
return OK;
}  

void main()  
{  ALGraph f;  
   printf("請輸入學(xué)期總數(shù):");  
   scanf("%d",&xqzs);  
   printf("請輸入學(xué)期的學(xué)分上限:");  
   scanf("%d",&xfsx);  
   CreateGraph(&f);
   printf("請選擇課程負(fù)擔(dān)均勻（輸入1）或課程向前集中（輸入2）：");
   scanf("%d",&pd);
   Display(f);  
   TopologicalSort(f);
}