#include?
#include?
#include?
#define?MAX_VERTEX_NUM?100?//最大課程總數(shù)
using?namespace?std;
struct?ArcNode
{
???????int?adjvex;//邊的終點(diǎn)
???????ArcNode?*nextarc;//指向下一條邊
};
typedef?struct?VNode
{
???????string?name;????????//課程名
???????string?classid;??????//課程號(hào)
???????int?credit;?????????//課程的學(xué)分
???????int?indegree;???????//該結(jié)點(diǎn)的入度
???????int?state;??????????//該節(jié)點(diǎn)的狀態(tài)
???????ArcNode?*firstarc;?//指向第一條依附該頂點(diǎn)的邊
}VNodeAdjList[MAX_VERTEX_NUM];//最初設(shè)定為100門課
typedef?int?ElemType;
struct?ALGraph
{
???????AdjList?vertices;
???????int?vexnum?arcnum;
};
class?stack
{
????private:
????struct?node
????{
????????int?data;
????????node?*next;
????????node（const?int?&xnode?*N=NULL）
????????{
????????????data=x;
????????????next=N;
????????}
????????node（）:next（NULL）{}
????????~node（）{};
????};
????node?*top_p;
?public?:
????stack（）;
????~stack（）;
????bool?isEmpty（）?const;
????void?push（const?int?&x）;
????int?pop（）;
};
stack::stack（）
{
????top_p=NULL;
}
stack::~stack（）
{
????node?*tmp;
????while（top_p!=NULL）
????{
????????tmp=top_p;
????????top_p=top_p->next;
????????delete?tmp;
????}
}
bool?stack::isEmpty（）?const
{
????return?top_p==NULL;
}
void?stack::push（const?int?&x）
{
????top_p=new?node?（xtop_p）;
}
int?stack::pop（）
{
????node?*tmp=top_p;
????int?x=tmp->data;
????top_p=top_p->next;
????delete?tmp;
????return?x;
}
void?CreatGraph（ALGraph?*G）//構(gòu)件圖
{???int?i?m?n;
????string?firstsecond;
????ArcNode?*p;
????cout<<“請(qǐng)輸入需要編排課程總數(shù):“<????cin>>G->vexnum;
????for（?i=1;i<=G->vexnum;i++）
????{???cout<<“請(qǐng)輸入課程名“<????????cin>>G->vertices[i].name;
????????cout<<“請(qǐng)輸入課程號(hào)“<????????cin>>G->vertices[i].classid;
????????cout<<“請(qǐng)輸入該課程的學(xué)分“<?????????cin>>G->vertices[i].credit;
????????G->vertices[i].indegree=0;
????????G->vertices?[i].state=0;
????????G->vertices[i].firstarc=NULL;
????}
????cout<<“請(qǐng)輸入課程先修關(guān)系總數(shù)：“<????cin>>G->arcnum;
????cout<<“請(qǐng)順序輸入每個(gè)課程先修關(guān)系（先修課程在前并以空格作為間隔）:“<????for?（i?=?1;?i?<=?G->arcnum;?i++）
????{
????????cout<????????cin>>first>>second;
????????for（int?j=1;j<=G->vexnum;j++）
????????{
????????????if（first==G->vertices[j].classid）
????????????{
????????????????n=j;
????????????????break;}

????????}
????????for（int?j=1;j<=G->vexnum;j++）
????????{
????????????if（second==G->vertices[j].classid）
????????????{
????????????????m=j;
????????????????break;}

????????}
????????p=new?ArcNode;
????????p->adjvex?=?m;
????????p->nextarc?=?G->vertices[n].firstarc;//插在表頭
????????G->vertices[n].firstarc?=?p;
????}
}
void?FindInDegree（ALGraph?G?int?indegree[]）//求圖中各節(jié)點(diǎn)的入度
{
????int?i;
????for?（i?=?1;?i?<=?G.vexnum;?i++）
????????indegree[i]?=?0;

????for?（i?=?1;?i?<=?G.vexnum;?i++）
????{
????????while?（G.vertices[i].firstarc）
????????{
????????????indegree[G.vertices[i].firstarc->adjvex]++;
????????????G.vertices[i].firstarc?=?G.vertices[i].firstarc